Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
image
Example:
Input: "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.
解法思路（一）
- 这是个排列组合问题对吧？这个排列组合可以用树的形式表示出来；
-
当给定了输入字符串，比如："23"，那么整棵树就构建完成了，如下：
算法过程.png - 问题转化成了从根节点到空节点一共有多少条路径；
解法实现（一）
时间复杂度
- O(2^len(s))；
空间复杂度
- O(len(s))；
关键字
排列组合 树 递归 递归带货
实现细节
- 在递归的外面有个货仓
res，用来装递归过程中找到的结果；
package leetcode._17;
import java.util.ArrayList;
import java.util.List;
public class Solution17_1 {
private String letterMap[] = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
private ArrayList<String> res;
public List<String> letterCombinations(String digits) {
res = new ArrayList<String>();
if(digits.equals(""))
return res;
findCombination(digits, 0, "");
return res;
}
private void findCombination(String digits, int index, String s){
if(index == digits.length()){
res.add(s);
return;
}
Character c = digits.charAt(index);
String letters = letterMap[c - '0'];
for(int i = 0 ; i < letters.length() ; i ++){
findCombination(digits, index+1, s + letters.charAt(i));
}
return;
}
}
