---恢复内容开始---
| 标题： | Letter Combinations of a Phone Number |
| 通过率： | 26.6% |
| 难度： | 中等 |
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
本题描述还是比较清楚的，就是给定一个数字的字符串，电话中每个数字都对用几个字母，那么将这个所以的组合都列出来。即有几个数字就有几个字母，
本题刚开始我也搞不明白，因为是个动态循环，也就是说如果是“123”就是三层循环，“1234”就是四层循环，看到这里也可以看出来这种类似“全排列”的题目一定跟树有关，那么本题就是二叉树的深度遍历过程，每一层的元素是由该数字对应的字母数量决定比如说“234”那么树形就是如下图所示：
那么就是一个递归循环，下面看java代码：
1 public class Solution { 2 public List<String> letterCombinations(String digits) { 3 List<String> result=new ArrayList<String>(); 4 String [] map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 5 char [] temp=new char[digits.length()]; 6 climbTree(0,digits,temp,result,map); 7 return result; 8 } 9 public void climbTree(int level,String digits,char [] temp,List<String> result,String[] map){ 10 if(level==digits.length()){ 11 result.add(String.valueOf(temp)); 12 return ; 13 } 14 for(int i=0;i<map[digits.charAt(level)-‘0‘].length();i++){ 15 temp[level]=map[digits.charAt(level)-‘0‘].charAt(i); 16 climbTree(level+1,digits,temp,result,map); 17 } 18 } 19 }
以下是python代码，摘自github：
1 class Solution: 2 # @return a list of strings, [s1, s2] 3 4 def letterCombinations(self, digits): 5 d = [‘‘, ‘‘, ‘abc‘, ‘def‘, ‘ghi‘, ‘jkl‘, ‘mno‘, ‘pqrs‘, ‘tuv‘, ‘wxyz‘] 6 7 def _get(step): 8 if step == N: 9 ret.append(‘‘.join(curr)) 10 return 11 ind = int(digits[step]) 12 for c in d[ind]: 13 curr.append(c) 14 _get(step + 1) 15 curr.pop() 16 17 ret = [] 18 curr = [] 19 N = len(digits) 20 _get(0) 21 return ret
leetcode------Letter Combinations of a Phone Number
原文：http://www.cnblogs.com/pkuYang/p/4274332.html