17.M 电话号码的字母组合

Problem: 17. 电话号码的字母组合

思路

回溯法。

定义一个map用来维护数字和字符集合的映射关系。对于每个数字，找到它所对应的字符集合，然后每次尝试使用其中一个字符，然后继续回溯下一个数字。当start等于digits的长度时，表示本轮回溯已经结束，直接把当前结果加到返回结果中。

Code

var digitToLetters = map[string]string{
	"2": "abc",
	"3": "def",
	"4": "ghi",
	"5": "jkl",
	"6": "mno",
	"7": "pqrs",
	"8": "tuv",
	"9": "wxzy",
}

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}

	var ans []string
	var cur = ""
	backtrace(digits, 0, cur, &ans)
	return ans
}

func backtrace(digits string, start int, cur string, ans *[]string) {
	if start == len(digits) {
		*ans = append(*ans, cur)
		return
	}

	digit := string(digits[start])
	letters := digitToLetters[digit]
	for i := 0; i < len(letters); i++ {
		backtrace(digits, start+1, cur+string(letters[i]), ans)
	}

}