Backtracking - 17. Letter Combinations of a Phone Number
Backtracking - 17. Letter Combinations of a Phone Number
ppxai
发布于 2020-09-23 17:32:25
发布于 2020-09-23 17:32:25
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.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
null
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
思路：
非常典型的dfs回溯法求所有解问题，因为问题可以画出一个递归树。做法就是递归求解字符串的每一位，枚举所有可能的组合。
代码：
go：
var dict = [][]string{
{},
{},
{"a", "c", "b"},
{"d", "e", "f"},
{"g", "h", "i"},
{"j", "k", "l"},
{"m", "n", "o"},
{"p", "q", "r", "s"},
{"t", "u", "v"},
{"w", "x", "y", "z"},
}
func letterCombinations(digits string) []string {
var res []string
if digits == "" || len(digits) == 0 {
return res
}
dfs(digits, 0, "", &res)
return res
}
func dfs(digits string, index int, temp string, res *[]string) {
if index == len(digits) {
*res = append(*res, temp)
return
}
idx := digits[index] - '0'
for _, c := range dict[idx] {
temp = temp + c
dfs(digits, index+1, temp, res)
temp = temp[0:len(temp)-1]
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年09月09日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读