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.
1 2(abc) 3(def)
4(ghi) 5(jkl) 6(mno)
7(pqrs) 8(tuv) 9(wxyz)
*+ 0_ ^#
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i] is a digit in the range ['2', '9'].
1
2
3
4
5
6
7
8
9
|
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
M = [0, 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
res = ['']
for c in digits:
res = [p+n for p in res for n in M[int(c)]]
return res
|
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
|
func letterCombinations(digits string) []string {
if digits == "" {
return []string{}
}
m := map[byte]string{
'0': "0",
'1': "1",
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz",
}
var res []string
backtrack("", &res, 0, digits, m)
return res
}
func backtrack(cur string, res *[]string, i int, digits string, m map[byte]string) {
if i == len(digits) {
*res = append(*res, cur)
return
}
for _, c := range m[digits[i]] {
backtrack(cur+string(c), res, i+1, digits, m)
}
}
|