0017.电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

方法一：回溯

时间复杂度 $O(3^m×4^n)$，空间复杂度 $O(m+n)$。

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	d := []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	var dfs func(digits string) []string

	dfs = func(digits string) []string {
		ans := []string{}
		if len(digits) == 0 {
			return []string{""}
		}
		subLetters := dfs(digits[1:])
		digit := int(digits[0] - '2')
		for i := 0; i < len(d[digit]); i++ {
			x := string(d[digit][i])
			for _, letter := range subLetters {
				ans = append(ans, x+letter)
			}
		}
		return ans
	}
	return dfs(digits)
}

方法二：遍历

时间复杂度 $O(3^m×4^n)$，空间复杂度 $O(4^n)$。

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	ans, d := []string{""}, []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

	for i := 0; i < len(digits); i++ {
		digit, t := d[digits[i]-'2'], []string{}
		for i := 0; i < len(digit); i++ {
			for _, v := range ans {
				t = append(t, v+string(digit[i]))
			}
		}
		ans = t
	}
	return ans
}