[leetcode] 17. Letter combination of telephone number

17. Letter combination of telephone number

Digression ：

Continue today LeetCode, I found that I was selected accidentally ,《 Data structure and algorithm field content list 》, It all depends on the support of all the big guys , Thank you thank you .

Next , Continue to brush the questions , analysis , I hope it can be used by students who want to learn algorithms , Help .

subject ：

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 .

Their thinking ：

The difficulty of this question is simple , First , See all the combinations , Your first reaction is probably to go back , Yes , you 're right , This problem can be solved by backtracking .

You can use one first map, To store all the letters corresponding to the numbers ..

Use backtracking , Exhaustively , List all possible solutions .

Reference code ：

class Solution {
    
    // Set the global list to store the final results 
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
    
        if (digits == null || digits.length() == 0) {
    
            return list;
        }
        // The initial number corresponds to all the numbers , For direct correspondence 2-9, Added two invalid strings ""
        String[] numString = {
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        // Iterative processing 
        backTracking(digits, numString, 0);
        return list;

    }

    // Get one string per iteration , So we will design a lot of string splicing , So choose the more efficient one here  StringBuild
    StringBuilder temp = new StringBuilder();

    // such as digits If "23",num  by 0, be str Express 2 Corresponding  abc
    public void backTracking(String digits, String[] numString, int num) {
    
        // Traversing all the strings at one time, recording the string obtained at one time 
        if (num == digits.length()) {
    
            list.add(temp.toString());
            return;
        }
        //str  At present num The corresponding string 
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
    
            temp.append(str.charAt(i));
            //c
            backTracking(digits, numString, num + 1);
            // Remove the last one and try again 
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}