12.电话号码的数字组合-回溯法

思路

递归，广度优先，参考二叉树的前中后序遍历

package main

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	var numString = map[string][]string{
		"2": {"a", "b", "c"},
		"3": {"d", "e", "f"},
		"4": {"g", "h", "i"},
		"5": {"j", "k", "l"},
		"6": {"m", "n", "o"},
		"7": {"p", "q", "r", "s"},
		"8": {"t", "u", "v"},
		"9": {"w", "x", "y", "z"},
	}
	result := make([]string, 0)
	var dfs func(int, string)
	dfs = func(i int, path string) {
		if i >= len(digits) {
			result = append(result, path)
			return
		}
		for _, v := range numString[string(digits[i])] {
			dfs(i+1, path+v)
		}
	}

	dfs(0, "")
	return result
}