# 17. Letter Combinations of a Phone Number

## 10 Jan 17. 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. Return the answer in any order.

A mapping of digits 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"
```

Example 2:

```Input: digits = ""
Output: []
```

Example 3:

```Input: digits = "2"
Output: ["a","b","c"]
```

Constraints:

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

# 理解题目

``````class Solution:
def letterCombinations(self, digits):
table = {
'2':"abc", '3':"def", '4':"ghi",
'5':"jkl", '6':"mno", '7':"pqrs",
'8':"tuv", '9':"wxyz"
}
def dfs(ans, cur, idx):
nonlocal digits
if idx == len(digits):
ans.append(cur)
else:
for letter in table[digits[idx]]:
dfs(ans, cur+letter, idx+1)
return ans
return dfs([], "", 0) if digits else []
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

# 迭代解法

`0 <= digits.length <= 4`

• 先取第一个数字初始化一下结果列表`ans`
• 初始化结束后，会开始遍历剩余的数字
• 对于接下来的每个数字`digit`，把`ans`中的每个可能结果和这个数字对应的字母们`table[digit]`做笛卡尔乘积(`Cartesian product`)，会得到一个新的`ans`
• 不断循环这个过程，直到所有数字被遍历过，最终返回`ans`
``````class Solution:
def letterCombinations(self, digits):
if not digits: return []
table = {
'2':"abc", '3':"def", '4':"ghi",
'5':"jkl", '6':"mno", '7':"pqrs",
'8':"tuv", '9':"wxyz"
}
ans = list(table[digits[0]])
for digit in digits[1:]:
ans = [exist + c for exist in ans for c in table[digit]] # 这一句等同于下面五句
# tmp = []
# for exist in ans:
#     for c in table[digit]:
#         tmp.append(exist + c)
# ans = tmp
return ans

``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

# 解题后的思考

class Solution:
def letterCombinations(self, digits: str) -> List[str]:
dictionary = {
“2” : “abc”,
“3” : “def”,
“4” : “ghi”,
“5” : “jkl”,
“6” : “mno”,
“7” : “pqrs”,
“8” : “tuv”,
“9” : “wxyz”,
}
if len(digits) == 0:
return []
first = digits[0]
results = list(dictionary[first])
for digit in digits[1:]:
tmp = []
for i in results:
for j in dictionary[digit]:
tmp.append(i+j)
results = tmp
return results