This article is participating in Python Theme Month. See the link to the event for more details

describe

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

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

Example 2:

Input: digits = ""
Output: []
Copy the code

Example 3:

Input: digits = "2"
Output: ["a","b","c"]
Copy the code

Note:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
Copy the code

parsing

The numbers from 2 to 9 are similar to those of an old dialing telephone (or now you can open the dial of your mobile phone and see the contents of each key against the question). 2 stands for the letters A, B and C, 3 for d, E and F, 4 for g, H and I. 5 represents J, K, and L; 6 represents M, N, and O; 7 represents P, Q, r, and S; 8 represents T, u, and V; and 9 represents W, x, y, and z. The question asks you to return all possible combinations of letters that each numeric character represents, based on the number in the digits string given.

I don’t know how many loops I should write. I don’t know how many loops I should write. You can try this. Use the dictionary D to write down the letters for each numeric character, and then each time you recurse, determine if the digits length is 0 and return an empty list. Return the list(d[digits]) if length is 1, otherwise recursively order the characters in digits[:-1], and when the result is returned, combine it one by one with each result in this level of recursive d[digits[-1]]. At the end of the recursion, you get a list of all the combinations. The idea is very simple, dubugging the details of the code will be clear.

answer

class Solution(object): def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ d = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'} if len(digits) == 0: return [] if len(digits) == 1: return list(d[digits]) tail = self.letterCombinations(digits[:-1]) other = d[digits[-1]] return [s + c for s in tail for  c in other]Copy the code

The results

Runtime: 10000 ms, the linked list for Letter column of a Phone Number. Each node in the given list has a range of 10000 mbit/s.Copy the code

Link: leetcode.com/problems/le…

Your support is my greatest motivation