题目描述#

给定一个只包含数字 2-9 的字符串 digits，要求返回它能够表示的所有字母组合。数字和字母的对应关系与电话九宫格按键一致，其中 1 不对应任何字母。

如果输入为空字符串，就没有可以组合的内容，直接返回空数组。

思路#

这题是很典型的回溯题：每个数字对应一组候选字母，我们要从每一组里选一个字母，按顺序拼成长度为 len(digits) 的字符串。嘿嘿，像是在给每一位数字拍一张“候选字母照片”，最后把照片按顺序贴成相册～

递归函数 dfs(i) 表示当前正在处理第 i 位数字。先通过 digits[i]-'0' 找到这一位数字对应的字母集合，然后枚举其中每个字母，把它放到 path[i] 里，再递归处理下一位。等 i == n 时，说明每一位都已经填好了，此时把 path 转成字符串加入答案。

这里用固定长度的 path 复用中间结果，而不是每次递归都创建新字符串，可以让实现更清爽。由于每一层只负责一个数字，递归天然保证了组合长度正确；如果 digits 为空，则没有递归入口，直接返回空切片。没错没错，回溯最重要的就是“当前位置做选择，然后交给下一层”，本姑娘看了都想给它咔嚓一张～

时间复杂度取决于所有组合数量。每个数字最多对应 4 个字母，所以最坏情况下组合数是 4^n，生成每个字符串需要 O(n)，整体可以看作 O(n * 4^n)；额外空间主要是递归栈和路径数组，为 O(n)，不计返回结果。

思维边界#

• 回溯建模：每一层递归对应 digits 的一个位置，每层枚举该数字能选择的所有字母。
• 路径复用：path 用 []byte 固定长度保存当前组合，递归过程中直接覆盖当前位置即可。
• 终止条件：当 i == n 时，说明一个完整组合已经构造完成，此时再加入答案。
• 空输入处理：digits 为空时应返回空数组，而不是返回包含空字符串的数组。
• 字符索引转换：digits[i]-'0' 用来把数字字符转成整数下标，前提是题目保证只包含 2-9。

代码#

func letterCombinations(digits string) []string {
	// 回溯问题
	var mapping = [...]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	n := len(digits)
	if n == 0 {
		return []string{}
	}
	var dfs func(int)
	ans := []string{}
	path := make([]byte, n)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, string(path))
			return
		}
		for _, c := range mapping[digits[i]-'0'] {
			path[i] = byte(c)
			dfs(i + 1)
		}
	}
	dfs(0)
	return ans
}