0017-电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = ""
输出:[]
示例 3:
输入:digits = "2"
输出:["a","b","c"]
提示:
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
参考:
- https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dai-ma-sui-xiang-lu-17-dian-hua-hao-ma-d-ya2x/
python
# 0017-电话号码的字母组合
class Solution:
def letterCombinations(self, digits: str) -> [str]:
res = []
s = ""
letterMap = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
if not len(digits):
return res
def backTrack(digits, index):
nonlocal s
if index == len(digits):
return res.append(s)
digit = int(digits[index])
letters = letterMap[digit]
for i in range(len(letters)):
s += letters[i]
backTrack(digits, index+1)
s = s[:-1] # 回溯
backTrack(digits, 0)
return res
golang
package backTrack
func letterCombinations(digits string) []string {
length := len(digits)
if length == 0 || length > 4 {
return nil
}
letterMap := [10]string{
"", //0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
}
res := make([]string, 0)
recursion("", digits, 0,letterMap, &res)
return res
}
func recursion(tmpstring, digits string, index int, letterMap [10]string, res *[]string) {
if len(tmpstring) == len(digits) {
*res = append(*res, tmpstring)
return
}
tmpK := digits[index] - '0' // index指向的数字转为int
letters := letterMap[tmpK]
for i:=0;i