电话号码的字母组合

题目

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：“23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

答案

class Solution { public List<String> letterCombinations(String digits) { List<String> ans=new ArrayList<String>(); if (digits.length()==0){ return ans; } //使用Map键值对来存入电话号码对应的字母 Map<Character,String> phoneMap = new HashMap(); phoneMap.put('2',"abc"); phoneMap.put('3',"def"); phoneMap.put('4',"ghi"); phoneMap.put('5',"jkl"); phoneMap.put('6',"mno"); phoneMap.put('7',"pqrs"); phoneMap.put('8',"tuv"); phoneMap.put('9',"wxyz"); backtrack(phoneMap,digits,0,ans,new StringBuffer()); return ans; } public void backtrack(Map<Character,String> phoneMap,String digits,int index,List<String> ans,StringBuffer sb){ //用sb来存入当前进行的组合，ans来存入所有答案 //当sb的长度等于号码长度时，组合完成，获得一个答案 if (sb.length() == digits.length()){ ans.add(sb.toString()); }else { //根据index获取电话号码，再获取对应字符 //s为某一个数字对应的所有字母的集合 String s=phoneMap.get(digits.charAt(index)); //依次取出s中的每一个字符 for (int i=0;i<s.length();i++){ //将当前字符添加到sb中 sb.append(s.charAt(i)); //index+1，即调用下一个数字，使用递归获得下一个数字的字母 backtrack(phoneMap,digits,index+1,ans,sb); //当前字母使用后删除，空出位置 //随着i增加，s下一个字母填充当前位置 sb.deleteCharAt(sb.length()-1); } } } }