add 97 problem solution

6boris · 6boris · commit f8d150ba881b · 2019-03-23T20:48:51.000+08:00
diff --git a/src/0000.Demo/README.md b/src/0000.Demo/README.md
@@ -23,12 +23,12 @@ Output: "10101"
 **Tags:** Math, String
 
 ## 题意
->给你两个二进制串，求其和的二进制串。
+> 求2数之和
 
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+> 。。。。
 
 ```go
 
diff --git a/src/0097.Interleaving-String/README.md b/src/0097.Interleaving-String/README.md
@@ -1,37 +1,63 @@
-# [1. Add Sum][title]
+# [97. Interleaving String][title]
 
 ## Description
 
-Given two binary strings, return their sum (also a binary string).
-
-The input strings are both **non-empty** and contains only characters `1` or `0`.
-
+Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
 **Example 1:**
 
 ```
-Input: a = "11", b = "1"
-Output: "100"
+Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
+Output: true
 ```
 
 **Example 2:**
 
 ```
-Input: a = "1010", b = "1011"
-Output: "10101"
+Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
+Output: false
 ```
 
 **Tags:** Math, String
 
 ## 题意
->给你两个二进制串，求其和的二进制串。
+>给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
+ 
 
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+>
 
 ```go
-
+func isInterleave2(s1 string, s2 string, s3 string) bool {
+	if len(s3) != len(s1)+len(s2) {
+		return false
+	}
+
+	dp := make([][]bool, len(s1)+1)
+	for i := 0; i < len(s1)+1; i++ {
+		dp[i] = make([]bool, len(s2)+1)
+	}
+
+	dp[0][0] = true
+	for i := 1; i < len(s1)+1; i++ {
+		if s1[i-1] == s3[i-1] {
+			dp[i][0] = dp[i-1][0]
+		}
+	}
+
+	for j := 1; j < len(s2)+1; j++ {
+		if s2[j-1] == s3[j-1] {
+			dp[0][j] = dp[0][j-1]
+		}
+	}
+	for i := 1; i < len(s1)+1; i++ {
+		for j := 1; j < len(s2)+1; j++ {
+			dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || (s2[j-1] == s3[i+j-1] && dp[i][j-1])
+		}
+	}
+	return dp[len(s1)][len(s2)]
+}
 ```
 
 ### 思路2
@@ -44,5 +70,5 @@ Output: "10101"
 
 如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
 
-[title]: https://leetcode.com/problems/two-sum/description/
+[title]: https://leetcode.com/problems/interleaving-string/
 [me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0097.Interleaving-String/Solution.go b/src/0097.Interleaving-String/Solution.go
@@ -1,5 +1,65 @@
 package Solution
 
-func Solution(x bool) bool {
-	return x
+import "fmt"
+
+func isInterleave(s1 string, s2 string, s3 string) bool {
+	if len(s3) != len(s2)+len(s1) {
+		return false
+	}
+	dp := make([][]bool, len(s1)+1)
+	for i := 0; i < len(s2)+1; i++ {
+		dp[i] = make([]bool, len(s2)+1)
+	}
+	dp[0][0] = true
+
+	for i := 0; i < len(s1)+1; i++ {
+		for j := 0; j < len(s2)+1; j++ {
+			if i == 0 && j == 0 {
+				dp[i][j] = true
+			} else if i == 0 {
+				dp[i][j] = dp[i][j-1] && s2[j-1] == s3[i+j-1]
+			} else if j == 0 {
+				dp[i][j] = dp[i-1][j] && s1[i-1] == s3[i+j-1]
+			} else {
+				dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) ||
+					(dp[i][j-1] && s2[j-1] == s3[i+j-1])
+			}
+		}
+	}
+	return dp[len(s1)][len(s2)]
+}
+
+func isInterleave2(s1 string, s2 string, s3 string) bool {
+	if len(s3) != len(s1)+len(s2) {
+		return false
+	}
+
+	dp := make([][]bool, len(s1)+1)
+	for i := 0; i < len(s1)+1; i++ {
+		dp[i] = make([]bool, len(s2)+1)
+	}
+
+	dp[0][0] = true
+	for i := 1; i < len(s1)+1; i++ {
+		if s1[i-1] == s3[i-1] {
+			dp[i][0] = dp[i-1][0]
+		}
+	}
+
+	for j := 1; j < len(s2)+1; j++ {
+		if s2[j-1] == s3[j-1] {
+			dp[0][j] = dp[0][j-1]
+		}
+	}
+	for i := 1; i < len(s1)+1; i++ {
+		for j := 1; j < len(s2)+1; j++ {
+			dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || (s2[j-1] == s3[i+j-1] && dp[i][j-1])
+		}
+	}
+	return dp[len(s1)][len(s2)]
+}
+func p(x [][]bool) {
+	for i := 0; i < len(x); i++ {
+		fmt.Println(x[i])
+	}
 }
diff --git a/src/0097.Interleaving-String/Solution_test.go b/src/0097.Interleaving-String/Solution_test.go
@@ -9,26 +9,56 @@ func TestSolution(t *testing.T) {
 	//	测试用例
 	cases := []struct {
 		name   string
-		inputs bool
+		inputs []string
 		expect bool
 	}{
-		{"TestCacse 1", true, true},
-		{"TestCacse 1", true, true},
-		{"TestCacse 1", false, false},
+		{"TestCase", []string{
+			"aabcc", "dbbca", "aadbbcbcac",
+		}, true},
+		{"TestCase", []string{
+			"aabcc", "dbbca", "aadbbbaccc",
+		}, false},
 	}
 
 	//	开始测试
 	for _, c := range cases {
 		t.Run(c.name, func(t *testing.T) {
-			ret := Solution(c.inputs)
-			if !reflect.DeepEqual(ret, c.expect) {
+			got := isInterleave(c.inputs[0], c.inputs[1], c.inputs[2])
+			if !reflect.DeepEqual(got, c.expect) {
 				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
-					c.expect, ret, c.inputs)
+					c.expect, got, c.inputs)
 			}
 		})
 	}
 }
 
+
+func TestSolution2(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		inputs []string
+		expect bool
+	}{
+		{"TestCase", []string{
+			"aabcc", "dbbca", "aadbbcbcac",
+		}, true},
+		{"TestCase", []string{
+			"aabcc", "dbbca", "aadbbbaccc",
+		}, false},
+	}
+
+	//	开始测试
+	for _, c := range cases {
+		t.Run(c.name, func(t *testing.T) {
+			got := isInterleave2(c.inputs[0], c.inputs[1], c.inputs[2])
+			if !reflect.DeepEqual(got, c.expect) {
+				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
+					c.expect, got, c.inputs)
+			}
+		})
+	}
+}
 //	压力测试
 func BenchmarkSolution(b *testing.B) {
 
