ninehills / blog

https://ninehills.tech
862 stars 80 forks source link

LeetCode-17. Letter Combinations of a Phone Number #26

Closed ninehills closed 7 years ago

ninehills commented 7 years ago

问题:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

image

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

思路

一次循环

解答

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        digit_map = {
            '1': [''],
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z'],
            '0': [' ']
        }
        old = set([''])
        for i in digits:
            new = set()
            for z in digit_map[i]:
                for k in old:
                    new.add(k + z)
            old = new
        return list(new)

print Solution().letterCombinations("23024")
ninehills commented 7 years ago

20170726