【leetcode】17. Letter combination of telephone number

subject ：
17. Letter combination of telephone number
Given a number only 2-9 String , Returns all the letter combinations it can represent . You can press In any order return .
The mapping of numbers to letters is given as follows （ Same as phone key ）. Be careful 1 Does not correspond to any letter .

Example 1：

Input ：digits = “23”
Output ：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
Example 2：

Input ：digits = “”
Output ：[]
Example 3：

Input ：digits = “2”
Output ：[“a”,“b”,“c”]

Tips ：
0 <= digits.length <= 4
digits[i] Is the scope of [‘2’, ‘9’] A number of .

to flash back :
The backtracking algorithm has three main points ：

1. choice
   Determines which branches you have at each node , Help you build a spatial tree of solutions .
   The choice of this question is , Multiple letters corresponding to each number , Choose to translate into one of the letters , Just continue recursion
2. constraint condition
   For pruning , Cut out the subtree that does not meet the constraints , Avoid invalid searches . This question doesn't seem to reflect
3. The goal is
   Determines when to capture solutions , Or cut the subtree that cannot be solved , Backtracking in advance . When the pointer of the scanned number reaches the end, the solution can be added to the solution set .

Ideas ：

1. Starting from the root node , After arriving at a node , A series of choices will be made to update the path according to the current status and topic meaning (path) The elements in .

• Status path (path) In this question, it means the element in a combination .
• In this question, we will select a letter from the currently available letter set and put it in path in .
• In addition, we use a hash table to store the mapping between numbers and letters

2. When the leaf node is reached , Indicates that a combination has been found .
3. After arriving at the leaf node, we will go back , That is, return to the previous node , Then make a new choice to calculate another combination .

• path It's like a stack structure , While returning to the previous node , You need to delete path The last element added to the .

4. After traversing the leaf nodes of the entire tree , It means you have found all the combinations .

dfs + to flash back :

class Solution {
    
    List<String> result = new ArrayList<>();
    Map<Character, String> map = new HashMap<Character, String>(){
    {
    
        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 result;
        }
        backtracking(digits, 0, new StringBuilder());
        return result;
    }
    public void backtracking(String digits, int start, StringBuilder path) {
    
        if (path.length() == digits.length()) {
    
            result.add(path.toString());
            return;
        }
        String letters = map.get(digits.charAt(start));
        for (int j = 0; j < letters.length(); j++) {
    
            path.append(letters.charAt(j));
            backtracking(digits, start + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
}