17. 电话号码的字母组合

[yankewei]

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

[yankewei]

一看这种组合，全排列，就可以想到使用回溯算法。回溯算法的本质就是求出所有的可能解，遍历所有的可能答案。

var ret []string
var m = map[byte][]byte{
    '2': []byte{'a', 'b', 'c'},
    '3': []byte{'d', 'e', 'f'},
    '4': []byte{'g', 'h', 'i'},
    '5': []byte{'j', 'k', 'l'},
    '6': []byte{'m', 'n', 'o'},
    '7': []byte{'p', 'q', 'r', 's'},
    '8': []byte{'t', 'u', 'v'},
    '9': []byte{'w', 'x', 'y', 'z'},
}
func letterCombinations(digits string) []string {
    if digits == "" {
        return []string{}
    }
    ret = []string{}
    dfs(digits, 0, []byte{})
    return ret
}

func dfs(digits string, index int, promot []byte) {
    if len(digits) == len(promot) {
	ret = append(ret, string(promot))
	return
    }
    for _, v := range m[digits[index]] {
	promot = append(promot, v)
	dfs(digits, index+1, promot)
	promot = promot[:len(promot)-1]
    }
}