forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathletter_combination.py
More file actions
40 lines (36 loc) · 790 Bytes
/
letter_combination.py
File metadata and controls
40 lines (36 loc) · 790 Bytes
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
32
33
34
35
36
37
38
39
40
"""
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:
2: "abc"
3: "def"
4: "ghi"
5: "jkl"
6: "mno"
7: "pqrs"
8: "tuv"
9: "wxyz"
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
"""
def letter_combinations(digits):
if digits == "":
return []
kmaps = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
ans = [""]
for num in digits:
tmp = []
for an in ans:
for char in kmaps[num]:
tmp.append(an + char)
ans = tmp
return ans