Repository navigation
Expand file tree
/
Copy path_87_isScramble.java
More file actions
110 lines (105 loc) · 3.46 KB
/
Copy path_87_isScramble.java
File metadata and controls
110 lines (105 loc) · 3.46 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
package pp.arithmetic.leetcode;
/**
* Created by wangpeng on 2019-11-05.
* 87. 扰乱字符串
*
* 下图是字符串 s1 = "great" 的一种可能的表示形式。
*
* great
* / \
* gr eat
* / \ / \
* g r e at
* / \
* a t
* 在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
*
* 例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat" 。
*
* rgeat
* / \
* rg eat
* / \ / \
* r g e at
* / \
* a t
* 我们将 "rgeat” 称作 "great" 的一个扰乱字符串。
*
* 同样地，如果我们继续交换节点 "eat" 和 "at" 的子节点，将会产生另一个新的扰乱字符串 "rgtae" 。
*
* rgtae
* / \
* rg tae
* / \ / \
* r g ta e
* / \
* t a
* 我们将 "rgtae” 称作 "great" 的一个扰乱字符串。
*
* 给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
*
* 示例 1:
*
* 输入: s1 = "great", s2 = "rgeat"
* 输出: true
* 示例 2:
*
* 输入: s1 = "abcde", s2 = "caebd"
* 输出: false
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/scramble-string
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class _87_isScramble {
public static void main(String[] args) {
_87_isScramble isScramble = new _87_isScramble();
System.out.println(isScramble.isScramble("great","rgeat"));
System.out.println(isScramble.isScramble("abcde","caebd"));
}
/**
* 解题思路：
* 对于两个字符串，比较是否相等，有两种情景
* 1：字符串本身就相等
* 2：基于某个节点交换后相等==>此种情况可以将旋转后的子字符串代入第一种情况进行判断
*
* 对于上述两种情况可以将字符串分解成两部分（从0开始拆解）
*
* @param s1
* @param s2
* @return
*/
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
if (s1.equals(s2)) {
return true;
}
//判断两个字符串每个字母出现的次数是否一致
int[] letters = new int[26];
for (int i = 0; i < s1.length(); i++) {
letters[s1.charAt(i) - 'a']++;
letters[s2.charAt(i) - 'a']--;
}
//如果两个字符串的字母出现不一致直接返回 false
for (int i = 0; i < 26; i++) {
if (letters[i] != 0) {
return false;
}
}
//遍历每个切割位置
for (int i = 1; i < s1.length(); i++) {
//对应情况 1 ，判断 S1 的子树能否变为 S2 相应部分
if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
return true;
}
//对应情况 2 ，S1 两个子树先进行了交换，然后判断 S1 的子树能否变为 S2 相应部分
if (isScramble(s1.substring(i), s2.substring(0, s2.length() - i)) &&
isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) ) {
return true;
}
}
return false;
}
}