Leetcode/各大家 -- 17. Letter Combinations of a Phone Numbe(backtracking)

17. Letter Combinations of a Phone Number (bakctracking)
medium
https://leetcode.com/problems/letter-combinations-of-a-phone-number/

 Dropbox Google Uber Facebook

思路： - iterate each digit while check its letter recursively
            - when iterating digit, path.length is index
           eg　- ad*, ae*, af* (* means looping current char)
                  - bd* be* bf*
                  - cd*....           
Complexity: Time O((3or4)^n) every digit has 3 or 4 options, Space O(n) - map

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
        if(digits.length()==0)return res;
        HashMap<Character,char[]> map = new HashMap<Character,char[]>();
        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'});
        StringBuilder sb = new StringBuilder();
        dfs(digits,map,res,sb);
        return res;
    }
    public void dfs(String digits,HashMap<Character,char[]>map,List<String>res,StringBuilder sb){
        if(sb.length()==digits.length()){
            res.add(sb.toString());
            return;
        }//cur digit index is sb.length()
        for(char c:map.get(digits.charAt(sb.length()))){//char index is sb length
            sb.append(c);
            dfs(digits,map,res,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}