-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathScrambleString.java
More file actions
67 lines (62 loc) · 2.28 KB
/
ScrambleString.java
File metadata and controls
67 lines (62 loc) · 2.28 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
public class ScrambleString {
boolean isScramble(String s1, String s2) {
if(s1.equals(s2))
return true;
boolean[][][] scrambled = new boolean[s1.length()][s2.length()][s1.length() + 1];
for(int i = 0; i < s1.length(); i++)
for(int j = 0; j < s2.length(); j++){
scrambled[i][j][0] = true;
scrambled[i][j][1] = s1.charAt(i) == s2.charAt(j);
}
for(int i = s1.length() - 1; i >= 0 ; i--)
for(int j = s2.length() - 1; j >= 0; j--)
for(int n = 2; n <= Math.min(s1.length() - i, s2.length() - j); n ++)
for(int m = 1; m < n; m++){
scrambled[i][j][n] |= scrambled[i][j][m] && scrambled[i + m][j + m][n - m] ||
scrambled[i][j + n - m][m] && scrambled[i + m][j][n - m];
if(scrambled[i][j][n]) break;
}
return scrambled[0][0][s1.length()];
}
/*
public boolean isScramble(String C, String T) {
if (T.length() != C.length()) {
return false;
} else if (T.length() == 1) {
return T.charAt(0) == C.charAt(0);
} else {
for (int i = 1; i < T.length(); i++) {
String t1 = T.substring(0, i);
String t2 = T.substring(i);
String c1 = C.substring(0, t1.length());
String c2 = C.substring(t1.length());
if (isEqualSet(t1, c1)) {
if (isScramble(t1, c1) && isScramble(t2, c2) ) {
return true;
}
}
c1 = C.substring(0, t2.length());
c2 = C.substring(t2.length());
if (isEqualSet(t1, c2)) {
if (isScramble(t1, c2) && isScramble(t2, c1)) {
return true;
}
}
}
return false;
}
}
private boolean isEqualSet(String A, String B) {
int[] set = new int[256];
for (char c : A.toCharArray()) {
set[c]++;
}
for (char c : B.toCharArray()) {
if (set[c]-- == 0) {
return false;
}
}
return true;
}
*/
}