This is the sixth day of my participation in the First Challenge 2022

Topic describes

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: who = "" output: [] example 3: input: Digits = "2" ["a","b"," C "] https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s algorithm of the day problem is the combination of letters in telephone numbers, which is clear and realistic. They’re asking us to enumerate all the combinations.
  • Firstly, we need to find the letters corresponding to digit according to digits, which is generally stored in the way of hashMap to improve the search efficiency.
  • Each digit corresponds to three letters in addition to the 1. Therefore, we need to traverse letters. For each letter, there are two cases of select and unselect, and we deal with them respectively.
  • The termination condition for DFS is the index position of the current digit, equal to digits.length(). The specific implementation code is as follows:

Through the code

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) {
            return ans;
        }

        Map<Character, String> phoneMap = 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");
        }};


        dfs(ans, phoneMap, digits, 0.new StringBuffer());

        return ans;
    }


    public void dfs(List<String> ans, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            ans.add(combination.toString());
            return;
        }

        char digit = digits.charAt(index);
        String letters = phoneMap.get(digit);
        int lettersCount = letters.length();
        for (int i = 0; i < lettersCount; i++) {
            combination.append(letters.charAt(i));
            dfs(ans, phoneMap, digits, index + 1, combination); combination.deleteCharAt(index); }}}Copy the code

conclusion

  • Today’s topic is very good, close to reality, easy to understand. Combined with DFS, HashMap and other knowledge assessment. We need to practice several times to master the comprehensive application of knowledge.
  • Adhere to the algorithm of the day, come on!