This is the 14th day of my participation in Gwen Challenge

preface

The letter combination of the phone number is as follows:

Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order.

The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.

Example 1:

Input: who = “23” output: [” AD “, “ae”, “af”, “bd”, “be”, “bf”, “CD” and “ce”, “cf”]

Example 2:

Input: digits = “”

Example 3:

[“a”,”b”,”c”]

A, thinking

This is a typical example of a problem that looks simple, but isn’t very easy to implement. The result of this problem is simple permutations and combinations. For example, there are 36 mappings for the three numbers 249 (3x3x4).

You can think of the result generation process as the tree starts at the root and expands from the top down. For example, 249 has three children from the root node to 2, three children from 2 to 4, and four children from 4 to 9.

As shown below:

As you can see from the figure above, the final result is always determined by the next node. This means that backtracking can be used to solve the problem.

The specific steps are as follows:

  • Find all the characters corresponding to the first key
  • Takes the first character of the first key
  • If there is a key, continue down until you find all the mapping results for the first key
  • The characters following the first key are treated as above

Second, the implementation

Code implementation

Backtracking is used here

Variable Description RET: result set phoneMap: dictionary table that stores the characters corresponding to cases

    public List<String> letterCombinations(String digits) {
        List<String> ret = new ArrayList<>();
        if (digits == null || digits.length() == 0)
            return ret;
        // Create a dictionary
        Map<String, char[]> phoneMap = new HashMap<>();
        phoneMap.put("2".new char[] {'a'.'b'.'c'});
        phoneMap.put("3".new char[] {'d'.'e'.'f'});
        phoneMap.put("4".new char[] {'g'.'h'.'i'});
        phoneMap.put("5".new char[] {'j'.'k'.'l'});
        phoneMap.put("6".new char[] {'m'.'n'.'o'});
        phoneMap.put("Seven".new char[] {'p'.'q'.'r'.'s'});
        phoneMap.put("8".new char[] {'t'.'u'.'v'});
        phoneMap.put("9".new char[] {'w'.'x'.'y'.'z'});
        backtrack(ret, phoneMap, digits, 0.new StringBuffer());
        return ret;
    }

    private void backtrack(List<String> combinations, Map<String, char[]> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            // Backtrace end condition
            combinations.add(combination.toString());
        } else {
            String digit = digits.substring(index, index+1);
            char[] letters = phoneMap.get(digit);
            for (char letter : letters) {
                combination.append(letter);
                backtrack(combinations, phoneMap, digits, index + 1, combination); combination.deleteCharAt(index); }}}Copy the code

The test code

    public static void main(String[] args) {
        new Number17().letterCombinations("23");
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥