题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
解题
方法一：回溯
class Solution { public: const string letterMap[10] = { "", // 0 "", // 1 "abc", // 2 "def", // 3 "ghi", // 4 "jkl", // 5 "mno", // 6 "pqrs", // 7 "tuv", // 8 "wxyz", // 9 }; vector<string> res; string s=""; void backtracing(string digits,int index){ if(index==digits.size()){ res.push_back(s); return; } int num=digits[index]-'0'; string letter=letterMap[num]; for(int i=0;i<letter.size();i++){ s+=letter[i]; backtracing(digits,index+1); s.pop_back(); } } vector<string> letterCombinations(string digits) { if(digits.empty()) return {}; backtracing(digits,0); return res; } };
java
class Solution { Map<Character,String> mp=new HashMap<>(){ { put('2',"abc"); put('3',"def"); put('4',"ghi"); put('5',"jkl"); put('6',"mno"); put('7',"pqrs"); put('8',"tuv"); put('9',"wxyz"); } }; List<String> res=new LinkedList<>(); StringBuilder path=new StringBuilder(); void dfs(String digits,int index){ if(path.length()==digits.length()){ res.add(path.toString()); return; } Character c=digits.charAt(index); String word=mp.get(c); for(int i=0;i<word.length();i++){ path.append(word.charAt(i)); dfs(digits,index+1); path.deleteCharAt(path.length()-1); } } public List<String> letterCombinations(String digits) { if(digits.equals("")) return new LinkedList<>(); dfs(digits,0); return res; } }
