我刚刚尝试进行我的第一次编程面试,其中一个问题是编写一个程序,给定一个 7 位数字的电话号码,可以打印每个数字可以代表的所有可能的字母组合。
问题的第二部分是如果这是一个 12 位国际号码怎么办?这将如何影响您的设计。
我没有在采访中编写的代码,但我的印象是他对此不满意。
最好的方法是什么?
I just tried for my first programming interview and one of the questions was to write a program that given a 7 digit telephone number, could print all possible combinations of letters that each number could represent.
A second part of the question was like what about if this would have been a 12 digit international number? How would that effect your design.
I don't have the code that I wrote in the interview, but I got the impression he wasn't happy with it.
What is the best way to do this?
发布评论
评论(30)
在Python中,迭代:
ret
是迄今为止的结果列表;最初它填充了一项,即空字符串。然后,对于输入字符串中的每个字符,它从顶部定义的字典中查找与其匹配的字母列表。然后,它用现有前缀和可能字母的每种组合替换列表ret
。In Python, iterative:
ret
is a list of results so far; initially it is populated with one item, the empty string. Then, for each character in the input string, it looks up the list of letters that match it from the dict defined at the top. It then replaces the listret
with the every combination of existing prefix and possible letter.它类似于电话号码的字母组合,
这是我的解决方案。
它适用于任意数量的数字,只要结果不超过内存限制即可。
我不确定 12 位国际号码如何影响设计。
编辑:国际号码也将得到处理
It is similar to a question called letter combinations of a phone number,
here is my solution.
It works for an arbitrary number of digits, so long as the result doesn't exceed the memory limit.
I'm not sure how 12-digit international numbers affect the design.
Edit: International numbers will also be handled
在Java中使用递归:
In Java using recursion:
显而易见的解决方案是将数字映射到键列表的函数,然后是生成可能组合的函数:
第一个很明显,第二个更成问题,因为您有大约 3^ 个数字组合,这可以是一个非常大的数字。
一种方法是将数字匹配为数字中的数字(以 4 为基数)的每种可能性,并实现一些接近计数器的东西(跳过某些实例,因为通常可映射到数字的字母少于 4 个) )。
更明显的解决方案是嵌套循环或递归,它们都不太优雅,但在我看来是有效的。
必须注意的另一件事是避免可扩展性问题(例如,将可能性保留在内存中等),因为我们正在讨论很多组合。
PS 这个问题的另一个有趣的延伸是本地化。
The obvious solution is a function to map a digit to a list of keys, and then a function that would generate the possible combinations:
The first is obvious, the second is more problematic because you have around 3^number of digits combinations, which can be a very large number.
One way to do it is to look at each possibility for digit matching as a digit in a number (on base 4) and implement something close to a counter (jumping over some instances, since there are usually less than 4 letters mappable to a digit).
The more obvious solutions would be nested loops or recursion, which are both less elegant, but in my opinion valid.
Another thing for which care must be taken is to avoid scalability issues (e.g. keeping the possibilities in memory, etc.) since we are talking about a lot of combinations.
P.S. Another interesting extension of the question would be localization.
在 C++ 中(递归):
可以使用“k”和“i”等于 0 来调用该函数。
任何需要更多插图来理解逻辑的人都可以将递归技术与以下输出结合起来:
In C++(recursive):
This function can be called with 'k' and 'i' equal to zero.
Anyone, who requires more illustration to understand the logic, can combine recursion technique with following output:
在数字键盘中,文本和数字位于同一个键上。例如,2 有“ABC”,如果我们想写入以“A”开头的任何内容,我们需要输入键 2 一次。如果我们想输入“B”,请按 2 键两次并三次以输入“C”。下面是此类键盘的图片。
键盘 http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard .png
给定如图所示的键盘和一个数字,列出按这些数字可能出现的所有单词。
例如,如果输入数字是 234,则可能出现的单词可以组成的有(按字母顺序排列):
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
我们先做一些计算。七个数字可以组成多少个单词,每个数字代表 n 个字母?对于第一个数字,我们最多有四个选择,对于第一个字母的每个选择,第二个数字最多有四个选择,依此类推。所以这是一个简单的数学,它将是 O(4^n)。由于键 0 和 1 没有任何对应的字母表,并且许多字符有 3 个字符,因此 4^n 将是单词数的上限,而不是最小单词数。
现在让我们做一些例子。
对于 234 以上的数字。你看到什么规律了吗?是的,我们注意到最后一个字符总是 G、H 或 I,每当将其值从 I 重置为 G 时,其左侧的数字就会发生变化。
同样,每当倒数第二个字母表重置其值时,倒数第三个字母表也会发生变化,依此类推。当我们生成所有单词时,第一个字符仅重置一次。这也可以从另一端来看。也就是说,每当位置 i 的字符发生变化时,位置 i+1 的字符就会遍历所有可能的字符,并产生连锁反应,直到到达终点。
因为 0 和 1 没有任何与它们关联的字符。我们应该中断,因为这些数字不会迭代。
我们采用第二种方法,因为使用递归很容易实现它。我们走到最后,一一回来。递归的完美条件。让我们搜索基本案例。
当我们到达最后一个字符时,我们打印该单词以及最后一个数字的所有可能字符并返回。简单的基本情况。当我们到达最后一个字符时,我们打印该单词以及最后一个数字的所有可能字符并返回。简单的基本情况。
以下是递归方法的 C 实现,用于打印与数字输入数字对应的所有可能的单词。请注意,输入数字表示为数组以简化代码。
输出:
时间复杂度:
上述代码的时间复杂度为 O(4^n),其中 n 是输入数字的位数。
参考文献:
http://www.flipkart.com/programming-interviews-expose-secrets-landing-your-next-job-3rd/p/itmdxghumef3sdjn?pid=9788126539116&affid=sandeepgfg
In numeric keyboards, texts and numbers are placed on the same key. For example 2 has “ABC” if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. below is picture of such keypad.
keypad http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png
Given a keypad as shown in diagram, and a n digit number, list all words which are possible by pressing these numbers.
For example if input number is 234, possible words which can be formed are (Alphabetical order):
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
Let’s do some calculations first. How many words are possible with seven digits with each digit representing n letters? For first digit we have at most four choices, and for each choice for first letter, we have at most four choices for second digit and so on. So it’s simple maths it will be O(4^n). Since keys 0 and 1 don’t have any corresponding alphabet and many characters have 3 characters, 4^n would be the upper bound of number of words and not the minimum words.
Now let’s do some examples.
For number above 234. Do you see any pattern? Yes, we notice that the last character always either G,H or I and whenever it resets its value from I to G, the digit at the left of it gets changed.
Similarly whenever the second last alphabet resets its value, the third last alphabet gets changes and so on. First character resets only once when we have generated all words. This can be looked from other end also. That is to say whenever character at position i changes, character at position i+1 goes through all possible characters and it creates ripple effect till we reach at end.
Since 0 and 1 don’t have any characters associated with them. we should break as there will no iteration for these digits.
Let’s take the second approach as it will be easy to implement it using recursion. We go till the end and come back one by one. Perfect condition for recursion. let’s search for base case.
When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.
Following is C implementation of recursive approach to print all possible word corresponding to a n digit input number. Note that input number is represented as an array to simplify the code.
Output:
Time Complexity:
Time complexity of above code is O(4^n) where n is number of digits in input number.
References:
http://www.flipkart.com/programming-interviews-exposed-secrets-landing-your-next-job-3rd/p/itmdxghumef3sdjn?pid=9788126539116&affid=sandeepgfg
在 JavaScript 中。 CustomCounter 类负责递增索引。然后输出不同的可能组合。
In JavaScript. A CustomCounter class takes care of incrementing indexes. Then just output the different possible combinations.
这个问题类似于这个leetcode问题。这是我针对这个问题提交给leetcode的答案(检查 github 和视频了解说明)。
因此,我们需要的第一件事是某种方法来保存数字的映射,我们可以为此使用映射:
上面的方法正在准备映射,我将使用的下一个方法是为所提供的数字提供映射:
这个问题可以使用回溯来解决,回溯解决方案通常具有一个结构,其中方法签名将包含:结果容器、临时结果、带索引的原始源等。因此方法结构将采用以下形式:
现在可以填充方法主体as(结果将保存在列表中,临时保存在字符串生成器等中)
最后,该方法可以调用为:
现在数字的最大映射字符可以是 4(例如 9 有 wxyz),回溯涉及详尽的搜索来探索所有可能的排列(状态空间树),因此对于大小为 n 的数字,我们将有 4x4x4....n 次,即复杂度为 O( 4^n)。
This problem is similar to this leetcode problem. Here is the answer I submitted for this problem to leetcode (check github and video for explanation).
So the very first thing we need is some way to hold the mappings of a digit and we can use a map for this:
The above method is preparing the map and next method I would use is to provide the mapping for provided digit:
This problem can be solved using backtracking and a backtracking solution generally has a structure where the method signature will contain: result container, temp results, original source with index etc. So the method structure would be of the form:
And now the method body can be filled as (result will be kept in a list, temp in string builder etc.)
And finally the method can be invoked as:
Now the max mapped chars for a digit can be 4 (e.g. 9 has wxyz) and backtracking involves exhaustive search to explore all possible arrangements (state space tree) so for a digit of size
n
we are going to have4x4x4....n times
i.e. complexity would beO(4^n)
.使用列表 L,其中 L[i] = 数字 i 可以表示的符号。
L[1] = @,.,! (例如)
L[2] = a,b,c
等等。
那么你可以这样做(伪 C):
假设每个列表包含 3 个字符,则 7 个数字有 3^7 种可能性,12 个数字有 3^12 种可能性,这是没有那么多。如果您需要所有组合,我看不出更好的方法。你可以避免递归之类的东西,但无论如何你都不会得到比这更快的东西。
Use a list L where L[i] = the symbols that digit i can represent.
L[1] = @,.,! (for example)
L[2] = a,b,c
Etc.
Then you can do something like this (pseudo-C):
Assuming each list contains 3 characters, we have 3^7 possibilities for 7 digits and 3^12 for 12, which isn't that many. If you need all combinations, I don't see a much better way. You can avoid recursion and whatnot, but you're not going to get something a lot faster than this no matter what.
Python 解决方案非常经济,并且因为它使用生成器,所以在内存使用方面非常高效。
显然,itertools.product 正在为您解决大部分问题。但自己写并不难。这是 go 中的一个解决方案,它小心翼翼地重新使用数组
result
来生成其中的所有解决方案,并使用闭包f
来捕获生成的单词。结合起来,这些在product
中使用了 O(log n) 内存。A Python solution is quite economical, and because it uses generators is efficient in terms of memory use.
Obviously
itertools.product
is solving most of the problem for you. But writing it oneself is not difficult. Here's a solution in go, which is careful to re-use the arrayresult
to generate all solutions in, and a closuref
to capture the generated words. Combined, these give O(log n) memory use insideproduct
.这是这个答案的C#端口。
代码
单元测试
This is the C# port of this answer.
Code
Unit Tests
Python 解决方案
Python solution with
C# 中的这个版本相当高效,并且适用于非西方数字(例如“1234567”)。
This version in C# is reasonably efficient, and it works for non-western digits (like "۱۲۳۴۵۶۷" for example).
Oracle SQL:可用于任何电话号码长度,并且可以轻松支持本地化。
Oracle SQL: Usable with any phone number length and can easily support localization.
这是一种针对疼痛 C 的方法。这个方法似乎无效(事实上我认为根本无效)。但它有一些有趣的方面。
这样做的好处是字符串的大小没有真正的限制(没有字符限制)这允许您如果需要,只需等待即可生成越来越长的字符串。
Here is one for pain C. This one is likley not efficet (in fact I don't think it is at all). But there are some intresting aspects to it.
Whats nice about this is that there is no real limit to the size of the string (no character limit) This allows you to generate longer and longer strings if need be just by waiting.
我是个新手,所以有错误的地方请指正。
第一件事是研究太空和时间复杂度。这真的很糟糕,因为它是阶乘
因此对于阶乘(7) = 5040,任何递归算法都可以。但对于阶乘(12) ~= 4 * 10^8 ,这可能会导致递归解决方案中的堆栈溢出。
所以我不会尝试递归算法。使用“Next Permutation”循环解决方案非常简单。
因此,我将创建数组 {0, 1, 2, 3, 4, 5} 并生成所有排列,并在打印时将它们替换为相应的字符,例如。 0=A, 5=F
接下来 Perm 算法的工作原理如下。例如,给定 1,3,5,4,下一个排列是 1,4,3,5
查找下一个排列的步骤。
从右到左,找到第一个递减的数字。例如3
从左到右,找到大于 3 的最小数字,例如。 4
交换这些数字作为反转子集。 1,4,5,3 反转子集 1,4,3,5
使用下一个排列(或旋转),您可以生成特定的排列子集,假设您要显示从特定电话号码开始的 1000 个排列。这可以帮助您避免将所有数字都存储在内存中。如果我将数字存储为 4 字节整数,则 10^9 字节 = 1 GB!。
I am rather a newbie so please correct me wherever I am wrong.
First thing is looking into space & time complexity. Which is really bad since it's factorial
so for factorial(7) = 5040 any recursive algorithm would do. But for factorial(12) ~= 4 * 10^8 which can cause stack overflow in recursive solution.
So I would not attempt a recursive algorithm. Looping solution is very straight forward using "Next Permutation".
So I would create and array {0, 1, 2, 3, 4, 5} and generate all permutation and while printing replace them with respective characters eg. 0=A, 5=F
Next Perm algorithm works as follows. eg Given 1,3,5,4 next permutation is 1,4,3,5
Steps for finding next perm.
From right to left, find first decreasing number. eg 3
From left to right, find lowest number bigger than 3 eg. 4
Swap these numbers as reverse the subset. 1,4,5,3 reverse subset 1,4,3,5
Using Next permutation ( or rotation) you generate specific subset of permutations, say you want to show 1000 permutations starting from a particular phone number. This can save you from having all numbers in memory. If I store numbers as 4 byte integers, 10^9 bytes = 1 GB !.
这是相同的工作代码..
它是每个步骤的递归,检查一系列中出现相同数字时每个组合的可能性......我不确定从复杂性的角度来看是否有更好的解决方案......
请告诉我有任何问题....
Here is the working code for the same..
its a recursion on each step checking possibility of each combinations on occurrence of same digit in a series....I am not sure if there is any better solution then this from complexity point of view.....
Please let me know for any issues....
您可以在此处找到源代码 (Scala) 和 此处是一个工作小程序。
由于 0 和 1 与字符不匹配,因此它们在数字中构建自然断点。但它们并不出现在每个数字中(开头的 0 除外)。较长的数字(例如从 9 位数字开始的 +49567892345)可能会导致 OutOfMemoryErrors。因此,最好将数字分成
等组,看看是否可以从较短的部分中理解。我写了一个这样的程序,并测试了朋友提供的一些数字,但很少发现短单词的组合,可以在字典中查找匹配,更不用说单个长单词了。
因此,我的决定是仅支持搜索,不支持完全自动化,通过显示可能的组合,鼓励手动拆分数字,也许可以多次。
所以我找到了+-RAD JUNG(+-自行车男孩)。
如果你接受拼写错误、缩写、外来词、数字作为单词、数字作为单词和名称,那么你找到解决方案的机会比不乱搞要好得多。
是人类可能观察到的东西——让算法找到这样的东西是相当困难的。
You find source (Scala) here and an working applet here.
Since 0 and 1 aren't matched to characters, they build natural breakpoints in numbers. But they don't occur in every number (except 0 at the beginning). Longer numbers like +49567892345 from 9 digits starting, can lead to OutOfMemoryErrors. So it would be better to split a number into groups like
to see, if you can make sense from the shorter parts. I wrote such a program, and tested some numbers from my friends, but found rarely combinations of shorter words, which could be checked in a dictionary for matching, not to mention single, long words.
So my decision was to only support searching, no full automation, by displaying possible combinations, encouraging splitting the number by hand, maybe multiple time.
So I found +-RAD JUNG (+-bycicle boy).
If you accept misspellings, abbreviations, foreign words, numbers as words, numbers in words, and names, your chance to find a solution is much better, than without fiddling around.
are things a human might observe - to make an algorithm find such things is rather hard.
这是C++11中的递归算法。
This is a recursive algorithm in C++11.
我重写了对此的最新答案(上面提到的),从 C 到 Java。我还添加了对 0 和 1(如 0 和 1)的支持,因为 555-5055 等数字根本不适用于上述代码。
这里是。一些评论被保留。
I rewrote the latest answer to this (referred above) , from C to Java. I also included the support for 0 and 1 (as 0 and 1) because numbers such as 555-5055 weren't working at all with the above code.
Here it is. Some comments are preserved.
Objective-C 中的一种选择:
One option in Objective-C:
我在 ruby 中尝试过,并想出了一种不同的方法,它可能效率不高,就像此时的时间和空间 O(?) ,但我喜欢它,因为它使用 Ruby 的内置 Array.product 方法。你怎么认为?
编辑:我在上面的Python中看到了一个非常相似的解决方案,但是当我添加我的答案时我没有看到它
I tried it in ruby, and came up with a different way of doing, it's probably not efficient, like time and space O(?) at this point, but I like it because it uses Ruby's builtin Array.product method. What do you think?
EDIT: I see a very similar solution in Python above, but I hadn't seen it when I added my answer
使用嵌套循环的 R 解决方案:
我发布了另一个更奇怪的 R 解决方案,使用更多循环和采样
An R solution using nested loops:
I posted another, more bizarre R solution using more loops and sampling on my blog.
该方法使用 R,首先将字典转换为其相应的数字表示形式,然后将其用作查找。
在我的机器上,转换只需要 1 秒(从大约 100,000 个单词的本机 Unix 字典转换),典型的最多 100 个不同数字输入的查找总共需要 0.1 秒:
This approach uses R and is based on first converting the dictionary to its corresponding digit representation, then using this as a look-up.
The conversion only takes 1 second on my machine (converting from the native Unix dictionary of about 100,000 words), and typical look-ups of up to 100 different digit inputs take a total of .1 seconds: