This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022.

The title

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"]Copy the code

Example 2

Input: digits = ""Copy the code

Example 3

["a","b","c"]Copy the code

prompt

  • 0 <= digits.length <= 4
  • Digits [I] is a number in the range [‘2’, ‘9’]

Answer key

Train of thought

A hash table is first used to store all possible letters for each number, and then a backtrack is performed.

A string is maintained during backtracking to represent the existing alphabetic permutation (an existing alphabetic permutation is incomplete if all digits of a phone number are not iterated). The string is initially empty. Every time take the phone number of a number, the number from hash table corresponding to all possible letters, and will be one of the letters is inserted into the existing alphabetical order, and then continue to process after the phone number of a number, until after the telephone number of all digital, namely receive a complete alphabetical order. It then rolls back and iterates through the rest of the alphabetic permutations.

The backtracking algorithm is used to find all possible solutions, and if one solution is found to be infeasible, the infeasible solution is discarded. In this case, because every letter for every number can be in a letter combination, there is no impossible solution, just enumerate all the solutions.

code

class Solution:
    def letterCombinations(self, digits: str) - >List[str] :
        if not digits:
            return list()
        
        phoneMap = {
            "2": "abc"."3": "def"."4": "ghi"."5": "jkl"."6": "mno"."Seven": "pqrs"."8": "tuv"."9": "wxyz",}def backtrack(index: int) :
            if index == len(digits):
                combinations.append("".join(combination))
            else:
                digit = digits[index]
                for letter in phoneMap[digit]:
                    combination.append(letter)
                    backtrack(index + 1)
                    combination.pop()

        combination = list()
        combinations = list()
        backtrack(0)
        return combinations
Copy the code

conclusion

Practice makes perfect, shortage in one; Success depends on forethought, destroyed by.