LeetCode - Scramble String
Problem description
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
Analysis
The first idea is to use divide and conquer.
there are two ways to test if two strings are match. The first one is substring(0,i) matches substring(0,i). Another is substring(0,i) matches substring(len-i);
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
class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2))
return true;
if (s1.equals(new StringBuilder(s2).reverse().toString())){
return true;
}
if (s1.length() != s2.length()){
return false;
}
int len = s1.length();
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i<len; i++){
char c1 = s1.charAt(i);
map.put(c1, map.getOrDefault(c1, 0) + 1);
char c2 = s2.charAt(i);
map.put(c2, map.getOrDefault(c2, 0) - 1);
}
for (Map.Entry<Character, Integer> entry:map.entrySet()){
if (entry.getValue() != 0){
return false;
}
}
for (int i =1; i< len; i++){
String left1 = s1.substring(0, i);
String right1 = s1.substring(i);
String left2 = s2.substring(0,i);
String right2 = s2.substring(i);
if (isScramble(left1, left2) && isScramble(right1, right2)){
return true;
}
String left3 = s2.substring(0, len-i);
String right3 = s2.substring(len-i);
if (isScramble(left1, right3) && isScramble(right1, left3)){
return true;
}
}
return false;
}
}
An improvement is to use an array instead of the HashMap.
1
2
3
4
5
6
7
8
9
10
// 判断两个字符串每个字母出现的次数是否一致
int[] letters = new int[26];
for (int i = 0; i < s1.length(); i++) {
letters[s1.charAt(i) - 'a']++;
letters[s2.charAt(i) - 'a']--;
}
for (int i = 0; i < 26; i++) {
if(letters[i] != 0)
return false;
}
What to improve
- make sure don’t miss any other situations.