17-电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

例如：

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

输入：digits = ""
输出：[]

输入：digits = "2"
输出：["a","b","c"]

/*
 * @lc app=leetcode.cn id=17 lang=golang
 *
 * [17] 电话号码的字母组合
 */

// @lc code=start
func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}

	// 1. 建立映射表
	m := make(map[byte][]byte)
	m['2'] = []byte{'a', 'b', 'c'}
	m['3'] = []byte{'d', 'e', 'f'}
	m['4'] = []byte{'g', 'h', 'i'}
	m['5'] = []byte{'j', 'k', 'l'}
	m['6'] = []byte{'m', 'n', 'o'}
	m['7'] = []byte{'p', 'q', 'r', 's'}
	m['8'] = []byte{'t', 'u', 'v'}
	m['9'] = []byte{'w', 'x', 'y', 'z'}

	// 2. 回溯
	res := make([]string, 0)
	backtrack(m, digits, 0, []byte{}, &res)
	return res
}

func backtrack(m map[byte][]byte, digits string, index int, path []byte, res *[]string) {
	// 2.1 终止条件
	if index == len(digits) {
		*res = append(*res, string(path))
		return
	}

	// 2.2 处理当前层逻辑
	for _, v := range m[digits[index]] {
		path = append(path, v)
		// 2.3 进入下一层
		backtrack(m, digits, index+1, path, res)
		// 2.4 清理当前层
		path = path[:len(path)-1]
	}
}

// @lc code=end