LeetCode_Letter Combinations of a Phone Number

Posted on | Edited on | In | Views:

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
（根据九宫格键盘将数字映射到字符）

Example:



1. map / hash_table 进行索引

这个问题很直观就是建立一个map进行索引。在提交过程中，发现如果考虑了digits == ''的情况，时间大幅度降低。说明在这种测试情况下，多考虑一些极端情况，直接返回结果，会使得整体的测试时间减少很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        
        dict = {
            '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']
        }
        
        result = []
        for ch in digits:
            letter = dict[ch]
            if len(result) == 0:
                result = letter
            else:
                new_result = []
                for a in result:
                    for b in letter:
                        new_result.append(a + b)
                result = new_result
                
        return result