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.
解法思路（一）
- 這是個(gè)排列組合問(wèn)題對(duì)吧掏秩？這個(gè)排列組合可以用樹(shù)的形式表示出來(lái)农猬；
-
當(dāng)給定了輸入字符串，比如："23"，那么整棵樹(shù)就構(gòu)建完成了，如下：
算法過(guò)程.png - 問(wèn)題轉(zhuǎn)化成了從根節(jié)點(diǎn)到空節(jié)點(diǎn)一共有多少條路徑；
解法實(shí)現(xiàn)（一）
時(shí)間復(fù)雜度
- O(2^len(s))酷誓；
空間復(fù)雜度
- O(len(s))；
關(guān)鍵字
排列組合 樹(shù) 遞歸 遞歸帶貨
實(shí)現(xiàn)細(xì)節(jié)
- 在遞歸的外面有個(gè)貨倉(cāng)
res态坦，用來(lái)裝遞歸過(guò)程中找到的結(jié)果盐数；
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;
}
}
