如何打印出给定电话号码可能代表的所有可能的字母组合？

Question

我刚试过第一次编程访谈,其中一个问题是编写了一个给出7位数电话号码的程序,可以打印每个号码可能代表的所有可能的字母组合.

问题的第二部分就是如果这是一个12位数的国际号码呢？这会对你的设计产生什么影响.

我没有在采访中写的代码,但我得到的印象是他对此不满意.
做这个的最好方式是什么？

Answer 1

在Python中,迭代:

digit_map = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

def word_numbers(input):
  input = str(input)
  ret = ['']
  for char in input:
    letters = digit_map.get(char, '')
    ret = [prefix+letter for prefix in ret for letter in letters]
  return ret

ret是目前为止的结果清单; 最初它填充了一个项目,空字符串.然后,对于输入字符串中的每个字符,它会从顶部定义的字典中查找与其匹配的字母列表.然后它用ret现有前缀和可能的字母的每个组合替换列表.

Answer 2

它类似于一个叫做电话号码的字母组合的问题,这是我的解决方案.
它适用于任意数量的数字,只要结果不超过内存限制即可.

import java.util.HashMap;
public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preres = new ArrayList<String>();
        res.add("");

        for(int i = 0; i < digits.length(); i++) {
            String letters = map.get(digits.charAt(i));
            if (letters.length() == 0)
                continue;
            for(String str : res) {
                for(int j = 0; j < letters.length(); j++)
                    preres.add(str + letters.charAt(j));
            }
            res = preres;
            preres = new ArrayList<String>();
        }      
        return res;
    }

    static final HashMap<Character,String> map = new HashMap<Character,String>(){{
        put('1', "");
        put('2',"abc");
        put('3',"def");
        put('4',"ghi");
        put('5',"jkl");
        put('6',"mno");
        put('7',"pqrs");
        put('8',"tuv");
        put('9',"wxyz");
        put('0', "");
    }} ;
}

我不确定12位数的国际数字如何影响设计.

编辑:国际号码也将被处理

Answer 3

显而易见的解决方案是将数字映射到键列表的函数，然后是生成可能组合的函数：

第一个很明显，第二个则更成问题，因为您有大约 3^ 个数字组合，这可能是一个非常大的数字。

一种方法是将数字匹配为数字中的数字（以 4 为基数）的每种可能性，并实现一些接近计数器的东西（跳过某些实例，因为通常可映射到数字的字母少于 4 个） ）。

更明显的解决方案是嵌套循环或递归，它们都不太优雅，但在我看来是有效的。

必须注意的另一件事是避免可扩展性问题（例如，将可能性保留在内存中等），因为我们正在讨论很多组合。

PS 这个问题的另一个有趣的延伸是本地化。