Description
Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
1
2
3
4
5
6
7
| great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
|
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
1
2
3
4
5
6
7
| rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
|
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
1
2
3
4
5
6
7
| rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
|
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Example 1:
1
2
| Input: s1 = "great", s2 = "rgeat"
Output: true
|
Example 2:
1
2
| Input: s1 = "abcde", s2 = "caebd"
Output: false
|
Solution
You may considering the string is not always split at the middle.
The tree could be like this:
1
2
3
4
5
6
| great
/ \
g reat
/ \
r eat
...
|
Divide And Conquer (Top to Down)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| func isScramble(s1 string, s2 string) bool {
if s1 == s2 {
return true
}
length := len(s1)
// couting letters
var count [26]int
for i := 0; i < length; i++ {
count[s1[i]-'a']++
count[s2[i]-'a']--
}
// Does letters same?
for i := 0; i < 26; i++ {
if count[i] != 0 {
return false
}
}
for k := 1; k < length; k++ {
if isScramble(s1[k:], s2[k:]) && isScramble(s1[:k], s2[:k]) {
return true
}
// exchange substrings
if isScramble(s1[k:], s2[:length-k]) && isScramble(s1[:k], s2[length-k:]) {
return true
}
}
return false
}
|
Dynamic Programming (Bottom to Up)
Definition dp[l][i][j]:
s1[i] start from 'i's2[j] start from 'j''l' is the length of substring, the length in recursive solution.
Initialization dp[1][i][j] = (s1[i] == s2[j] ? true : false).
1
2
3
4
5
6
| dp[l][i][j] =
// isScramble(s1[k:], s2[k:]) && isScramble(s1[:k], s2[:k])
(dp[k][i][j] && dp[l-k][i+k][j+k]) ||
// isScramble(s1[k:], s2[:length-k]) && isScramble(s1[:k], s2[length-k:])
(dp[k][i][j+l-k] && dp[l-k][i+k][j])
|
k means split the l to two parts, so 0 <= k <= l;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| func isScramble(s1 string, s2 string) bool {
if len(s1) != len(s2) {
return false
}
length := len(s1)
dp := make([][][]bool, length+1)
for i := 0; i <= length; i++ {
dp[i] = make([][]bool, length)
for j := 0; j < length; j++ {
dp[i][j] = make([]bool, length)
}
}
for i := 0; i < length; i++ {
for j := 0; j < length; j++ {
dp[1][i][j] = (s1[i] == s2[j])
}
}
for l := 2; l <= length; l++ {
for i := 0; i < length-l+1; i++ {
for j := 0; j < length-l+1; j++ {
if dp[l][i][j] {
continue
}
for k := 1; k < l && (!dp[l][i][j]); k++ {
dp[l][i][j] = (dp[k][i][j] && dp[l-k][i+k][j+k]) ||
(dp[k][i][j+l-k] && dp[l-k][i+k][j])
}
}
}
}
return dp[length][0][0]
}
|