Merge pull request halfrost#61 from xxgail/patch-1

halfrost · halfrost · commit 2363839e94c6 · 2020-08-28T11:21:22.000+08:00
Update 0017.Letter-Combinations-of-a-Phone-Number.md
diff --git a/leetcode/0017.Letter-Combinations-of-a-Phone-Number/17. Letter Combinations of a Phone Number.go b/leetcode/0017.Letter-Combinations-of-a-Phone-Number/17. Letter Combinations of a Phone Number.go
@@ -66,3 +66,39 @@ func letterCombinations_(digits string) []string {
 	}
 	return tmp
 }
+
+// 解法三 回溯（参考回溯模板，类似DFS）
+var result []string
+var dict = 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"},
+}
+
+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]
+	}
+}
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]
+	}
+}
 
 ```
