Update 0017.Letter-Combinations-of-a-Phone-Number.md

xxgail · web-flow · commit fa6c7580048f · 2020-08-27T15:37:41.000+08:00
Update 0017.Letter-Combinations-of-a-Phone-Number 参考回溯模板，增加回溯的解法（类似于DFS）
diff --git a/website/content/ChapterFour/0017.Letter-Combinations-of-a-Phone-Number.md b/website/content/ChapterFour/0017.Letter-Combinations-of-a-Phone-Number.md
@@ -104,6 +104,41 @@ func letterCombinations_(digits string) []string {
 	return tmp
 }
 
+// 解法三 回溯（参考回溯模板，类似DFS）
+var result []string
+var dict = map[string][]string{
+	"2" : []string{"a","b","c"},
+	"3" : []string{"d", "e", "f"},
+	"4" : []string{"g", "h", "i"},
+	"5" : []string{"j", "k", "l"},
+	"6" : []string{"m", "n", "o"},
+	"7" : []string{"p", "q", "r", "s"},
+	"8" : []string{"t", "u", "v"},
+	"9" : []string{"w", "x", "y", "z"},
+}
+
+func letterCombinationsBT(digits string) []string {
+	result = []string{}
+	if digits == "" {
+		return result
+	}
+	letterFunc("", digits)
+	return result
+}
 
+func letterFunc(res string, digits string) {
+	if digits == "" {
+		result = append(result, res)
+		return
+	}
+
+	k := digits[0:1]
+	digits = digits[1:]
+	for i := 0; i < len(dict[k]); i++ {
+		res += dict[k][i]
+		letterFunc(res, digits)
+		res = res[0 : len(res)-1]
+	}
+}
 
 ```
