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

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

问题的第二部分就是如果这是一个12位数的国际号码呢? 这对你的设计有什么影响。

我没有在面试中写的代码,但我得到的印象是他对此并不满意。
最好的方法是?

时间:

在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

它类似于一个电话号码的字母组合,这是我的解决方案。
只要结果不超过内存限制,就可以使用任意数量的数字。


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-digit 国际数字如何影响设计。

编辑:国际数字也将被处理。

在Java中使用递归:


import java.util.LinkedList;


import java.util.List;



public class Main { 


//Number-to-letter mappings in order from zero to nine


 public static String mappings[][] = {


 {"0"}, {"1"}, {"A","B","C"}, {"D","E","F"}, {"G","H","I"},


 {"J","K","L"}, {"M","N","O"}, {"P","Q","R","S"}, 


 {"T","U","V"}, {"W","X","Y","Z"}


 };



 public static void generateCombosHelper(List<String> combos, 


 String prefix, String remaining) {


//The current digit we are working with


 int digit = Integer.parseInt(remaining.substring(0, 1));



 if (remaining.length() == 1) {


//We have reached the last digit in the phone number, so add 


//all possible prefix-digit combinations to the list


 for (int i = 0; i <mappings[digit].length; i++) {


 combos.add(prefix + mappings[digit][i]);


 }


 } else {


//Recursively call this method with each possible new 


//prefix and the remaining part of the phone number.


 for (int i = 0; i <mappings[digit].length; i++) {


 generateCombosHelper(combos, prefix + mappings[digit][i], 


 remaining.substring(1));


 }


 }


 }



 public static List<String> generateCombos(String phoneNumber) {


//This will hold the final list of combinations


 List<String> combos = new LinkedList<String>();



//Call the helper method with an empty prefix and the entire 


//phone number as the remaining part.


 generateCombosHelper(combos,"", phoneNumber);



 return combos;


 }



 public static void main(String[] args) {


 String phone ="3456789";


 List<String> combos = generateCombos(phone);



 for (String s : combos) {


 System.out.println(s);


 }


 }


}



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

第一个是显而易见的,第二个更有问题,因为你有大约3 ^个数字组合,这可能是一个非常大的数字。

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

更明显的解决方案是嵌套循环或者递归,这两者都不太优雅,但在我看来。

必须注意的另一件事是避免可扩展性问题(例如, 保持记忆中的可能性等等)因为我们正在谈论很多组合。

附:问题的另一个有趣的扩展是本地化。

...