这道题很容易想到应该使用的是回溯算法,代码写法也是用最标准的回溯写法模板,回溯的思想就是这个遍历完回退一步继续向后遍历,应用一下回溯模板就可以做出来。
var kv = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
var res []string
backtrack(digits, &res, "", 0)
return res
}
func backtrack(digits string, res *[]string, tmp string, nums int) {
if len(digits) == nums {
*res = append(*res, tmp)
}else {
index, _ := strconv.Atoi(string(digits[nums]))
str := kv[index]
for i := 0;i < len(str);i ++ {
backtrack(digits, res, tmp+string(str[i]), nums+1)
}
}
}