class Solution {
    // DFS
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();// StringBuilder
    Map<Character, String> phoneMap = new HashMap<>(){{//哈希
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return res;
        }
        dfs(digits, 0);
        return res;
    }
    private void dfs(String digits, int idx){
        if(idx == digits.length()){
            res.add(path.toString());// toString
            return;
        }
        char c = digits.charAt(idx);
        String letter = phoneMap.get(c);
        for(int i = 0; i < letter.length(); i++){
            path.append(letter.charAt(i));
            dfs(digits, idx + 1);
            path.deleteCharAt(idx);//恢复现场
        }
    }
}