二刷17. Letter Combinations of a Phone Number

Medium
这题用DFS,注意下每次搜索遍历的下一个字符是digits.charAt(sb.length().然后要backtracking.

class Solution {
    public List letterCombinations(String digits) {
        List res = new ArrayList<>();
        if (digits == null || digits.length() == 0){
            return res;
        }
        Map> map = new HashMap<>();
        map.put(2, new ArrayList(Arrays.asList('a','b','c')));
        map.put(3, new ArrayList(Arrays.asList('d','e','f')));
        map.put(4, new ArrayList(Arrays.asList('g','h','i')));
        map.put(5, new ArrayList(Arrays.asList('j','k','l')));
        map.put(6, new ArrayList(Arrays.asList('m','n','o')));
        map.put(7, new ArrayList(Arrays.asList('p','q','r','s')));
        map.put(8, new ArrayList(Arrays.asList('t','u','v')));
        map.put(9, new ArrayList(Arrays.asList('w','x','y','z')));
        StringBuilder sb = new StringBuilder();
        dfsHelper(res, map, sb, digits);        
        return res;
    }
    
    private void dfsHelper(List res, Map> map, StringBuilder sb, String digits){
        if (sb.length() == digits.length()){
            res.add(sb.toString());
            return;
        }    
        for (char c : map.get(Character.getNumericValue(digits.charAt(sb.length())))){
            sb.append(c);
            dfsHelper(res, map, sb, digits);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

你可能感兴趣的