leetcode17电话号码的字母组合（String）

发表于 | 分类于

题目

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

示例

1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

题解

本题使用DFS的思想，curr表示当前访问到的字符串，currIdx表示访问digits的位置。例如：

输入”234“字符串，helper方法会一直访问到currIdx指向digits的最后一位，第一次得到”adg”，把它加入到List，然后回溯到”ad”,继续遍历到最后，把得到的字符串加入List,回溯到”a”，继续深度遍历…最后得到的List就是我们要求的结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class solution{
    public List<String> letterCombinations(String digits){
        List<String> res = new ArrayList<>();
        if(digits==null||digits.length()==0) return res;
        HashMap<Character,char[]> map = new HashMap<>();
        map.put('2',new char[]{'a','b','c'});
        map.put('3',new char[]{'d','e','f'});
        map.put('4',new char[]{'g','h','i'});
        map.put('5',new char[]{'j','k','l'});
        map.put('6',new char[]{'m','n','o'});
        map.put('7',new char[]{'p','q','r','s'});
        map.put('8',new char[]{'t','u','v'});
        map.put('9',new char[]{'w','x','y','z'});
        helper("",0,digits,res,map);
        return res;
    }
    
    public void helper(String curr,int currIdx,String digits,List<String> res,HashMap<Character,char[]> map){
        if(currIdx==digits.length()){
            res.add(curr);
        }else{
            char c = digits.charAt(currIdx);
            if(map.containsKey(c)){
                for(Character ch: map.get(c)){
                    helper(curr+ch,currIdx+1,digits,res,map);
                }
            }
            
        }
        
    }
}