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

Commit545a283

Browse files
authored
Merge pull request6boris#472 from 0xff-dev/87
Add solution and test-cases for problem 87
2 parents4c586a8 +92a9ee9 commit545a283

File tree

3 files changed

+118
-11
lines changed

3 files changed

+118
-11
lines changed
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
#[87.Scramble String][title]
2+
3+
##Description
4+
We can scramble a string s to get a string t using the following algorithm:
5+
6+
If the length of the string is 1, stop.
7+
8+
If the length of the string is > 1, do the following:
9+
10+
- Split the string into two non-empty substrings at a random index, i.e., if the string is`s`, divide it to`x` and`y` where`s = x + y`.
11+
-**Randomly** decide to swap the two substrings or to keep them in the same order. i.e., after this step,`s` may become`s = x + y` or`s = y + x`.
12+
- Apply step 1 recursively on each of the two substrings`x` and`y`.
13+
14+
Given two strings`s1` and`s2` of**the same length**, return`true` if`s2` is a scrambled string of`s1`, otherwise, return`false`.
15+
16+
**Example 1:**
17+
18+
```
19+
Input: s1 = "great", s2 = "rgeat"
20+
Output: true
21+
Explanation: One possible scenario applied on s1 is:
22+
"great" --> "gr/eat" // divide at random index.
23+
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
24+
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
25+
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
26+
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
27+
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
28+
The algorithm stops now, and the result string is "rgeat" which is s2.
29+
As one possible scenario led s1 to be scrambled to s2, we return true.
30+
```
31+
32+
**Example 2:**
33+
34+
```
35+
Input: s1 = "abcde", s2 = "caebd"
36+
Output: false
37+
```
38+
39+
**Example 3:**
40+
41+
```
42+
Input: s1 = "a", s2 = "a"
43+
Output: true
44+
```
45+
46+
##结语
47+
48+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-algorithm][me]
49+
50+
[title]:https://leetcode.com/problems/scramble-string
51+
[me]:https://github.com/kylesliu/awesome-golang-algorithm
Lines changed: 58 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,61 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
funcSolution(s1string,s2string)bool {
4+
a:=make([]int,26)
5+
cache:=make(map[string]bool)
6+
returnisScramble87([]byte(s1), []byte(s2),cache,chars1(a))
7+
}
8+
9+
funcchars1(baseS1 []int)func([]byte, []byte)bool {
10+
returnfunc(s1,s2 []byte)bool {
11+
fori:=0;i<26;i++ {
12+
baseS1[i]=0
13+
}
14+
fori:=0;i<len(s1);i++ {
15+
baseS1[s1[i]-'a']++
16+
baseS1[s2[i]-'a']--
17+
}
18+
fori:=0;i<26;i++ {
19+
ifbaseS1[i]!=0 {
20+
returnfalse
21+
}
22+
}
23+
returntrue
24+
}
25+
}
26+
27+
funcisScramble87(s1,s2 []byte,cachemap[string]bool,cmpfunc([]byte, []byte)bool)bool {
28+
ifv,ok:=cache[string(s1)+string(s2)];ok {
29+
returnv
30+
}
31+
ifstring(s1)==string(s2) {
32+
returntrue
33+
}
34+
ll:=len(s1)
35+
equal:=true
36+
fori:=0;i<ll;i++ {
37+
ifs1[i]!=s2[ll-1-i] {
38+
equal=false
39+
break
40+
}
41+
}
42+
ifequal {
43+
returntrue
44+
}
45+
if!cmp(s1,s2) {
46+
returnfalse
47+
}
48+
cache[string(s1)+string(s2)]=false
49+
forl:=1;l<ll;l++ {
50+
ifisScramble87(s1[:l],s2[:l],cache,cmp)&&isScramble87(s1[l:],s2[l:],cache,cmp) {
51+
cache[string(s1)+string(s2)]=true
52+
returntrue
53+
}
54+
// a,b/c, cba
55+
ifisScramble87(s1[:l],s2[ll-l:],cache,cmp)&&isScramble87(s1[l:],s2[:ll-l],cache,cmp) {
56+
cache[string(s1)+string(s2)]=true
57+
returntrue
58+
}
59+
}
60+
returnfalse
561
}

‎leetcode/1-100/0087.Scramble-String/Solution_test.go

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -9,30 +9,30 @@ func TestSolution(t *testing.T) {
99
//测试用例
1010
cases:= []struct {
1111
namestring
12-
inputsbool
12+
s1,s2string
1313
expectbool
1414
}{
15-
{"TestCacse 1",true,true},
16-
{"TestCacse1",true,true},
17-
{"TestCacse1",false,false},
15+
{"TestCacse 1","great","rgeat",true},
16+
{"TestCacse2","abcde","cadbd",false},
17+
{"TestCacse3","a","a",true},
1818
}
1919

2020
//开始测试
2121
for_,c:=rangecases {
2222
t.Run(c.name,func(t*testing.T) {
23-
ret:=Solution(c.inputs)
23+
ret:=Solution(c.s1,c.s2)
2424
if!reflect.DeepEqual(ret,c.expect) {
25-
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26-
c.expect,ret,c.inputs)
25+
t.Fatalf("expected: %v, but got: %v, with inputs: %v %v",
26+
c.expect,ret,c.s1,c.s2)
2727
}
2828
})
2929
}
3030
}
3131

32-
//压力测试
32+
//压力测试
3333
funcBenchmarkSolution(b*testing.B) {
3434
}
3535

36-
//使用案列
36+
//使用案列
3737
funcExampleSolution() {
3838
}

0 commit comments

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