87 Scramble String
87. Scramble String
1. Question
Given a strings1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation ofs1="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 stringss1_and_s2_of the same length, determine if_s2_is a scrambled string of_s1.
Example 1:
Input:
s1 = "great", s2 = "rgeat"
Output:
true
Example 2:
Input:
s1 = "abcde", s2 = "caebd"
Output:
false
2. Implementation
(1) Recursion
思路: 如果s1和s2长度不同,显然return false。然后由于题目的输入string都只含小写字母,所以我们为了判断两个string是否含有一样的character时,我们利用一个size为26的count数字计数,然后再扫一遍count数组,如果count数组的元素不为0,说明存在不同或者数量不一样的character,此时返回false. 注意这步是必要的,否则会超时。
最后就通过递归的方式调用isScramble, 找出scramble的分割点即可
class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) {
return true;
}
if (s1.length() != s2.length()) {
return false;
}
int[] count = new int[26];
// Check if s1 and s2 has the same characters
for (int i = 0; i < s1.length(); i++) {
++count[s1.charAt(i) - 'a'];
--count[s2.charAt(i) - 'a'];
}
for (int i = 0; i < 26; i++) {
if (count[i] != 0) {
return false;
}
}
int n = s1.length();
// Check if s1 and s2 are scrambled strings using recursion
for (int i = 1; i < n; i++) {
if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))
|| (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, n - i)))) {
return true;
}
}
return false;
}
}
(2) DP
3. Time & Space Complexity
Recursion: 时间复杂度O(4 ^ n), 空间复杂度O(n) 递归的深度是O(n)
Last updated
Was this helpful?