[数据结构与算法]leetcode-17 电话号码字母组合

回溯

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

测试样例

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

解题思路：

先将数字对应的字母用一个HashMap<Character,String>保存起来。在每一层遍历digits相应位的数字时从map中取出数字对应的String并遍历装入临时变量中。
停止回溯条件：临时变量cur.length() == digits.length();
每一层遍历顺序：每一层对从map中取出来的String进行遍历。

难点：

字符串尾追加操作：String.append(str.charAt(i));
字符串删除操作：String.deleteCharAt(index);

代码实现：

class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return new ArrayList<String>();
        Map<Character,String> map = new HashMap<Character,String>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        List<String> res = new LinkedList<>();
        dfs(digits,map,res,digits.length(),new StringBuffer(),0);
        return res;
    }
    public void dfs(String digits,Map<Character,String> map,List<String> res,int len,StringBuffer cur,int index){
        if(index == len){
            res.add(cur.toString());
            return;
        }
        char tmp = digits.charAt(index);
        String str = map.get(tmp);
        int l = str.length();
        for(int i = 0;i < l;i++){
            cur.append(str.charAt(i));
            dfs(digits,map,res,len,cur,index + 1);
            cur.deleteCharAt(index);
        }
    }
}