-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathScramble String.java
More file actions
executable file
·193 lines (162 loc) · 6.64 KB
/
Copy pathScramble String.java
File metadata and controls
executable file
·193 lines (162 loc) · 6.64 KB
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
H
1518594579
tags: DP, String, Interval DP
- 给两个string S, T. 检验他们是不是scramble string.
- scramble string 定义: string可以被分拆成binary tree的形式, 也就是切割成substring;
- 旋转了不是leaf的node之后, 形成新的substring, 这就是原来string的 scramble.
#### Interval DP 区间型
- 降维打击, 分割, 按照长度来dp.
- dp[i][j][k]: 数组S从index i 开始, T从index j 开始, 长度为k的子串, 是否为scramble string
##### Break down
- 一切两半以后, 看两种情况: , 或者不rotate这两半. 对于这些substring, 各自验证他们是否scramble.
- 不rotate分割的两半: S[part1] 对应 T[part1] && S[part2] 对应 T[part2].
- rotate分割的两半: S[part1] 对应 T[part2] && S[part2] 对应 T[part1].
##### Initialization
- len == 1的时候, 其实无法旋转, 也就是看S,T的相对应的index是否字符相等.
- initialization非常非常重要. 很神奇, 这个initailization 打好了DP的基础, 后面一蹴而就, 用数学表达式就算出了结果.
- input s1, s2 在整个题目的主要内容里面, 几乎没有用到, 只是用在initialization时候.
- More details, 看解答
```
/*
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":
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".
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".
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.
*/
/*
Thoughts:
Want to determin the given string S can be scramble/rotate to T.
With the tree formation, it leads us to think of the string in partition: can S[i,j] be scambled to T[i,j]?
If all substrings can be in scrambled format, it'll return true.
dp[i][j][h][k]: can S(i, j) be scrambled to T(h, k)?
Reduce it to dp[i][j][k]: starting from index i for S, index j for T, with length k.
Can the substrings be scramble?
End: want dp[0][0][n] to be srambled.
Need size to be boolean dp[n][n][n + 1]
with len == 0, always false
with len == 1, if S[i]==T[j], then true.
with len == 2, do dp;
increase length from 1 ~ len, perform dp.
Consider two conditions:
rotate parent string || not rotating parent string
*/
class Solution {
public boolean isScramble(String s1, String s2) {
if (s1 == null || s2 == null) {
return s1 == null && s2 == null;
}
if (s1.length() != s2.length()) {
return false;
}
if (s1.equals(s2)) {
return true;
}
int n = s1.length();
boolean[][][] dp = new boolean[n][n][n + 1];
int len = 1;
// Initialize with len = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
}
}
// len = 2
for (len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
for (int j = 0; j <= n - len; j++) {
for (int w = 1; w < len; w++) { // w = length of 1st substring
dp[i][j][len] |= dp[i][j][w] && dp[i + w][j + w][len - w]; // not rotating parent string
dp[i][j][len] |= dp[i][j + (len - w)][w] && dp[i + w][j][len - w]; // not rotating parent string
}
}
}
}
return dp[0][0][n];
}
}
/*
Thoughts:
两个string, 代号 S, T
中间砍一刀, 分开两边. 要么是左右交换, 要么是不交换.
首先有了dp[i][j][k][h]:
分隔开来的S[i, j] 跟 T[k, h]是否是scramble string?
want to have dp[0][n][0][n] == true
变成了4维数组. 优化:
4维数组, 但是自由度只有3: 有3个变量可以确定第四个变量:
因为scramble string的长度相等, 所以 j - I = h - k => h = j + k- I
也就是说, 我们可以降维, 不需要4维数组.
降维: 最后一个维度省略, 变成了 length为维度:
*** dp[i][j][k]: 数组S从index i 开始, T从index j 开始, 长度为k的子串, 是否为scramble string?
等式需要细心写出来:
分割scramble过后, 原string定为S, 生成的string定为T
分割开来一刀, 分别割成 S1,S2, 和 T1,T2
假设S/T的总长都是k, 而分割点割在了位置为w的地方.
两种情况:
子序列不换位置: 要求分割开来的S1和T1是scramble, S2和T2是scramble
S1和T1的关系: dp[i][j][w] => s1 从 index[i] 割 w length, s2从index[j]割了 w length; 是否是scramble string
S2和T2的关系: dp[i + w][j + w][k - w] => S2和T2都在割过w length后的地方, 也就是i+w, j+w; 长度是总长减去w: k - w.
子序列换位置:要求分开的s1和s2换位置; 也就是s1对应的t1, 现在跑到了后面的位置
S1和T1的关系: s1在原地, t1换到了后面: t1还是w length, 所以位置变成了 j + (k - w)
S2和T2的关系: s2照旧在i+w的位置, t2换到了最前面: index j
综合上面的 情况, 并且让w循环[1, k-1]
dp[i][j][k] = OR{dp[i][j][w] && dp[i + w][j + w][k - w]}, where w = [1, k-1]
OR
OR{dp[i][j + k - w][w] && dp[i + w][j][k - w]}, where w = [1, k-1]
*/
class Solution {
public boolean isScramble(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() != s2.length()) {
return false;
}
int n = s1.length();
boolean[][][] dp = new boolean[n][n][n + 1];
// len = 1
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
}
}
// len = 2
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
for (int j = 0; j <= n - len; j++) {
// dp[i][j][len] = false; // default is false as well
for (int w = 1; w < len; w++) {
dp[i][j][len] |= (dp[i][j][w] && dp[i + w][j + w][len - w]);
dp[i][j][len] |= (dp[i][j + len - w][w] && dp[i + w][j][len - w]);
}
}
}
}
return dp[0][0][n];
}
}
```