Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf8d150b

Browse files
committed
add 97 problem solution
1 parent56d6788 commitf8d150b

File tree

4 files changed

+140
-24
lines changed

4 files changed

+140
-24
lines changed

‎src/0000.Demo/README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,12 +23,12 @@ Output: "10101"
2323
**Tags:** Math, String
2424

2525
##题意
26-
>给你两个二进制串，求其和的二进制串。
26+
>求2数之和
2727
2828
##题解
2929

3030
###思路1
31-
>按照小学算数那么来做，用`carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
31+
>。。。。
3232
3333
```go
3434

Lines changed: 39 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,37 +1,63 @@
1-
#[1. Add Sum][title]
1+
#[97. Interleaving String][title]
22

33
##Description
44

5-
Given two binary strings, return their sum (also a binary string).
6-
7-
The input strings are both**non-empty** and contains only characters`1` or`0`.
8-
5+
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
96
**Example 1:**
107

118
```
12-
Input:a = "11",b = "1"
13-
Output:"100"
9+
Input:s1 = "aabcc",s2 = "dbbca", s3 = "aadbbcbcac"
10+
Output:true
1411
```
1512

1613
**Example 2:**
1714

1815
```
19-
Input:a = "1010",b = "1011"
20-
Output:"10101"
16+
Input:s1 = "aabcc",s2 = "dbbca", s3 = "aadbbbaccc"
17+
Output:false
2118
```
2219

2320
**Tags:** Math, String
2421

2522
##题意
26-
>给你两个二进制串，求其和的二进制串。
23+
>给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
24+
2725

2826
##题解
2927

3028
###思路1
31-
>按照小学算数那么来做，用`carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
29+
>
3230
3331
```go
34-
32+
funcisInterleave2(s1string,s2string,s3string)bool {
33+
iflen(s3) !=len(s1)+len(s2) {
34+
returnfalse
35+
}
36+
37+
dp:=make([][]bool,len(s1)+1)
38+
fori:=0; i <len(s1)+1; i++ {
39+
dp[i] =make([]bool,len(s2)+1)
40+
}
41+
42+
dp[0][0] =true
43+
fori:=1; i <len(s1)+1; i++ {
44+
if s1[i-1] == s3[i-1] {
45+
dp[i][0] = dp[i-1][0]
46+
}
47+
}
48+
49+
forj:=1; j <len(s2)+1; j++ {
50+
if s2[j-1] == s3[j-1] {
51+
dp[0][j] = dp[0][j-1]
52+
}
53+
}
54+
fori:=1; i <len(s1)+1; i++ {
55+
forj:=1; j <len(s2)+1; j++ {
56+
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])
57+
}
58+
}
59+
return dp[len(s1)][len(s2)]
60+
}
3561
```
3662

3763
###思路2
@@ -44,5 +70,5 @@ Output: "10101"
4470

4571
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
4672

47-
[title]:https://leetcode.com/problems/two-sum/description/
73+
[title]:https://leetcode.com/problems/interleaving-string/
4874
[me]:https://github.com/kylesliu/awesome-golang-leetcode
Lines changed: 62 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,65 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
import"fmt"
4+
5+
funcisInterleave(s1string,s2string,s3string)bool {
6+
iflen(s3)!=len(s2)+len(s1) {
7+
returnfalse
8+
}
9+
dp:=make([][]bool,len(s1)+1)
10+
fori:=0;i<len(s2)+1;i++ {
11+
dp[i]=make([]bool,len(s2)+1)
12+
}
13+
dp[0][0]=true
14+
15+
fori:=0;i<len(s1)+1;i++ {
16+
forj:=0;j<len(s2)+1;j++ {
17+
ifi==0&&j==0 {
18+
dp[i][j]=true
19+
}elseifi==0 {
20+
dp[i][j]=dp[i][j-1]&&s2[j-1]==s3[i+j-1]
21+
}elseifj==0 {
22+
dp[i][j]=dp[i-1][j]&&s1[i-1]==s3[i+j-1]
23+
}else {
24+
dp[i][j]= (dp[i-1][j]&&s1[i-1]==s3[i+j-1])||
25+
(dp[i][j-1]&&s2[j-1]==s3[i+j-1])
26+
}
27+
}
28+
}
29+
returndp[len(s1)][len(s2)]
30+
}
31+
32+
funcisInterleave2(s1string,s2string,s3string)bool {
33+
iflen(s3)!=len(s1)+len(s2) {
34+
returnfalse
35+
}
36+
37+
dp:=make([][]bool,len(s1)+1)
38+
fori:=0;i<len(s1)+1;i++ {
39+
dp[i]=make([]bool,len(s2)+1)
40+
}
41+
42+
dp[0][0]=true
43+
fori:=1;i<len(s1)+1;i++ {
44+
ifs1[i-1]==s3[i-1] {
45+
dp[i][0]=dp[i-1][0]
46+
}
47+
}
48+
49+
forj:=1;j<len(s2)+1;j++ {
50+
ifs2[j-1]==s3[j-1] {
51+
dp[0][j]=dp[0][j-1]
52+
}
53+
}
54+
fori:=1;i<len(s1)+1;i++ {
55+
forj:=1;j<len(s2)+1;j++ {
56+
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])
57+
}
58+
}
59+
returndp[len(s1)][len(s2)]
60+
}
61+
funcp(x [][]bool) {
62+
fori:=0;i<len(x);i++ {
63+
fmt.Println(x[i])
64+
}
565
}

‎src/0097.Interleaving-String/Solution_test.go

Lines changed: 37 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -9,26 +9,56 @@ func TestSolution(t *testing.T) {
99
//测试用例
1010
cases:= []struct {
1111
namestring
12-
inputsbool
12+
inputs[]string
1313
expectbool
1414
}{
15-
{"TestCacse 1",true,true},
16-
{"TestCacse 1",true,true},
17-
{"TestCacse 1",false,false},
15+
{"TestCase", []string{
16+
"aabcc","dbbca","aadbbcbcac",
17+
},true},
18+
{"TestCase", []string{
19+
"aabcc","dbbca","aadbbbaccc",
20+
},false},
1821
}
1922

2023
//开始测试
2124
for_,c:=rangecases {
2225
t.Run(c.name,func(t*testing.T) {
23-
ret:=Solution(c.inputs)
24-
if!reflect.DeepEqual(ret,c.expect) {
26+
got:=isInterleave(c.inputs[0],c.inputs[1],c.inputs[2])
27+
if!reflect.DeepEqual(got,c.expect) {
2528
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26-
c.expect,ret,c.inputs)
29+
c.expect,got,c.inputs)
2730
}
2831
})
2932
}
3033
}
3134

35+
36+
funcTestSolution2(t*testing.T) {
37+
//测试用例
38+
cases:= []struct {
39+
namestring
40+
inputs []string
41+
expectbool
42+
}{
43+
{"TestCase", []string{
44+
"aabcc","dbbca","aadbbcbcac",
45+
},true},
46+
{"TestCase", []string{
47+
"aabcc","dbbca","aadbbbaccc",
48+
},false},
49+
}
50+
51+
//开始测试
52+
for_,c:=rangecases {
53+
t.Run(c.name,func(t*testing.T) {
54+
got:=isInterleave2(c.inputs[0],c.inputs[1],c.inputs[2])
55+
if!reflect.DeepEqual(got,c.expect) {
56+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
57+
c.expect,got,c.inputs)
58+
}
59+
})
60+
}
61+
}
3262
//压力测试
3363
funcBenchmarkSolution(b*testing.B) {
3464

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp