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.

The sample1: Input: digits ="23"Output:"ad"."ae"."af"."bd"."be"."bf"."cd"."ce"."cf"]
Copy the code

Method a

Your own violence solution (not recommended), because the number length in the problem is not more than 4, so you can discuss separately.

def letterCombinations1(digits) :
    n = len(digits)
    if n == 0: return []
    ans = []
    d = {"2": "abc"."3": "def"."4": "ghi"."5": "jkl"."6": "mno"."Seven": "pqrs"."8": "tuv"."9": "wxyz"}
    if n == 1:
        for ch in d[digits]:
            ans.append(ch)
        return ans

    if n == 2:
        for ch1 in d[digits[0]] :for ch2 in d[digits[1]]:
                ans.append(ch1+ch2)
        return ans

    if n == 3:
        for ch1 in d[digits[0]] :for ch2 in d[digits[1]] :for ch3 in d[digits[2]]:
                    ans.append(ch1+ch2+ch3)
        return ans

    if n == 4:
        for ch1 in d[digits[0]] :for ch2 in d[digits[1]] :for ch3 in d[digits[2]] :for ch4 in d[digits[3]]:
                        ans.append(ch1+ch2+ch3+ch4)
        return ans
Copy the code

Method 2

The first thing that comes to mind when a question has words like “all combinations” is backtracking.

Main idea: use recursion, from top to bottom recursion to achieve deep search, define sub-problems, solve the original problem in the current recursive layer with the results of sub-problems.

def letterCombinations3(digits) :
    if not digits: return []  If the string is empty, return an empty array
    d = {"2": "abc"."3": "def"."4": "ghi"."5": "jkl"."6": "mno"."Seven": "pqrs"."8": "tuv"."9": "wxyz"}
    def backtrack(combination, nextdigit) :
        Recursive function @param Combination: some possible string combination of preceding digits @param NextDigit: Remaining digits """
        if len(nextdigit) == 0:
            Write the recursive exit first
            # recursive exit. When there are no numbers left, add the combination to the array
            res.append(combination)
        else:
            # Iterate over the letter corresponding to the first of the remaining digits
            for letter in d[nextdigit[0]] :Call recursive function traceback
                # Concatenate the corresponding letter of this number at the end of the combination, and remove the first digit from the remaining digits
                backtrack(combination + letter, nextdigit[1:])
    res = []
    backtrack("", digits)  # Call the recursive function. The initial combination is the empty string "" and nextDigit is the entire numeric string digits
    return res
Copy the code

Method three

Queue in reference to the link before the selection of answer code, their own code, the main idea is: each time through the combination of the original number, and again through the new number corresponding to the string, sequentially splicing in the back

def letterCombinations4(digits) :
    if not digits: return []  If the string is empty, return an empty array
    d = {"2": "abc"."3": "def"."4": "ghi"."5": "jkl"."6": "mno"."Seven": "pqrs"."8": "tuv"."9": "wxyz"}
    res = []  # An array to store the results
    for letter in digits:
        if len(res) == 0:
            # Iterate over the letters corresponding to the first number
            for ch in d[letter]:
                res.append(ch)
        else:
            Use an array to store all possible letter combinations of the original preceding number
            old_res = res.copy()
            # Iterate over all possible letter combinations of the preceding number
            for ch1 in old_res:
                # Append the letters corresponding to the next number to all possible letter combinations of the preceding number
                for ch2 in d[letter]:
                    res.append(ch1+ch2)
                # Delete the original preceding letter combination
                res.remove(ch1)
    return res
Copy the code

The way to select an answer is to queue up each letter of the first digits in the input, then queue up each letter of the second digit in the input element. Until you reach the end of digits. And then the element in the queue is what you want.

def letterCombinations5(digits) :
    if not digits: return []  If the string is empty, return an empty array
    phone = ['abc'.'def'.'ghi'.'jkl'.'mno'.'pqrs'.'tuv'.'wxyz']
    queue = [""]  Initialize the queue
    for digit in digits:
        for _ in range(len(queue)):
            tmp = queue.pop(0)  # TMP Records a letter combination of the current preceding digit and deletes it
            # instead of using int() to convert strings, use ASCII
            # convert numeric character to ASCII, 50 is ASCII for character "2"
            for letter in phone[ord(digit) - 50]:
                queue.append(tmp + letter)  Add TMP to queue with new letters
    return queue
Copy the code
Complexity analysis

The complexity of these algorithms is basically the same.

  • Time complexity: O(3M∗4N)O(3^M*4^N)O(3M∗4N). M is the number of three-letter digits in the input numeric string, and N is the number of four-letter digits.
  • Space complexity: O(3M∗4N)O(3^M*4^N)O(3M∗4N). A total of 3M∗4N3^M * 4^N3M∗4N results are generated.