17.电话号码的字母组合
题目描述
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
思路
1.这道题可以将字母的组合看做为树,对该树进行深度遍历便可以获得正确答案。
2.我们可以使用递归进行深度遍历,递归结束的条件就是电话号码的字符串为空。
具体树的形状如下图:
Java代码实现
private Map<String, String> phoneMap = new HashMap<String, String>() {{ 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> combinations = new ArrayList<>(); private void dfs(String digits,String combination){ if(digits.length() == 0) { combinations.add(combination); return; }else{ String cur = phoneMap.get(digits.substring(0,1)); for(int i=0;i<cur.length();i++){ dfs(digits.substring(1),combination+cur.charAt(i)); } } } public List<String> letterCombinations(String digits) { if(digits.length()>0){ dfs(digits,""); } return combinations; }
Golang代码实现
func letterCombinations(digits string) []string { mymap := make(map[string]string) mymap["2"] = "abc" mymap["3"] = "def" mymap["4"] = "ghi" mymap["5"] = "jkl" mymap["6"] = "mno" mymap["7"] = "pqrs" mymap["8"] = "tuv" mymap["9"] = "wxyz" if(len(digits) == 0) return res res := make([]string,0) letterCombinationsDfs("",digits,&res,mymap) return res } func letterCombinationsDfs(cur string,digits string,res *[]string,phoneMap map[string]string){ if len(digits) == 0{ *res = append(*res, cur) return } phone := phoneMap[digits[:1]] for i:=0; i<len(phone); i++{ letterCombinationsDfs(cur+phone[i:i+1],digits[1:],res,phoneMap) } }