Skip to content

Commit 351e1bc

Browse files
xiaoningningxiaoningning
committed
scramble string
1 parent ae451cc commit 351e1bc

2 files changed

Lines changed: 94 additions & 4 deletions

File tree

‎PuzzleCoding/src/ScrambleString.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
/**
2+
* Scramble string, for two strings, say str1 = “tiger” and str2 = “itreg”
3+
* <p/>
4+
* Scramble string, for two strings, say str1 = “tiger” and str2 = “itreg”
5+
* tiger
6+
* / \
7+
* ti ger
8+
* / \ / \
9+
* t i g er
10+
* / \
11+
* e r
12+
* <p/>
13+
* itreg
14+
* / \
15+
* it reg
16+
* / \ / \
17+
* t i g re
18+
* / \
19+
* e r
20+
* <p/>
21+
* In above case, since s1 can be generated from str2, that is, str1 can be generated from the partition tree,
22+
* which has the same leaf of str2, but the order of its child can be switched.
23+
* So str1 is said to be a scramble string of str2.
24+
* <p/>
25+
* A counter example is that Tiger and Tgrie are not scramble string of each other
26+
* <p/>
27+
* The principle of this approach goes as following
28+
* 1) Given two strings A and B, try to split each of them into two sub-strings sA1,sA2,sB1,
29+
* sB2 where sA1 and sB1 are anagrams and sA2 and sB2 are anagrams.
30+
* 2) If sA1 and sB1 are the scramble strings while sA2 and sBs are scramble strings,
31+
* then A and B should be scramble strings.
32+
* 3) Recursively analyze sA1 and sB1, sA2 and sB2 by start over from step 1).
33+
* <p/>
34+
* In previous example
35+
* <p/>
36+
* str1 = aabbbaccd, str2: aabcdbcba,
37+
* <p/>
38+
* They are split as: (aab)(bbaccd), (aab)(cdbcba) => compare bbaccd and cdbcba
39+
* They are split as: (bbac)(cd), (cd)(bcba) => compare bbac and bcba
40+
* They are split as: (b)(bac), b(cba) => (ba)(c) vs (c)(ba)
41+
*/
42+
public class ScrambleString {
43+
public static void main(String[] args) {
44+
// String s1 = "apple";
45+
// String s2 = "palpe";
46+
String s1 = "tiger";
47+
String s2 = "tgrie";
48+
49+
System.out.println(isScrambleStringRecursive(s1, s2));
50+
51+
s1 = "tiger";
52+
s2 = "itreg";
53+
54+
System.out.println(isScrambleStringRecursive(s1, s2));
55+
56+
}
57+
58+
public static boolean isScrambleStringRecursive(String s1, String s2) {
59+
if (s1.length() != s2.length())
60+
return false;
61+
62+
if (s1.equals(s2))
63+
return true;
64+
else {
65+
66+
for (int i = 0; i < s1.length() - 1; i++) {
67+
String s1a = s1.substring(0, i + 1);
68+
String s1b = s1.substring(i + 1);
69+
70+
String s2a = s2.substring(0, i + 1);
71+
String s2b = s2.substring(i + 1);
72+
73+
String s2ar = s2.substring(s2.length() - 1 - i);
74+
String s2br = s2.substring(0, s2.length() - 1 - i);
75+
76+
if ((isScrambleStringRecursive(s1a, s2a) && isScrambleStringRecursive(s1b, s2b)) ||
77+
(isScrambleStringRecursive(s1a, s2ar) && isScrambleStringRecursive(s1b, s2br))) {
78+
return true;
79+
}
80+
81+
}
82+
return false;
83+
}
84+
}
85+
}

‎PuzzleCoding/src/StringAnagram.java‎

Lines changed: 9 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,12 +2,15 @@
22

33
public class StringAnagram {
44
public static void main(String[] args) {
5-
String s1 = "apple";
6-
String s2 = "pplae";
5+
// String s1 = "apple";
6+
// String s2 = "palpe";
7+
String s1 = "tiger";
8+
String s2 = "tgrie";
79

810
System.out.println(isAnagram(s1, s2));
911
System.out.println(isPermutation(s1, s2));
1012

13+
1114
}
1215

1316
public static String stringSort(String s) {
@@ -52,10 +55,12 @@ public static boolean isPermutation(String s1, String s2) {
5255
letter[c]--;
5356
}
5457

55-
for(int i = 0; i < letter.length; ++i){
56-
if((letter[i]>0) ||(letter[i]<0))
58+
for (int i = 0; i < letter.length; ++i) {
59+
if ((letter[i] > 0) || (letter[i] < 0))
5760
return false;
5861
}
5962
return true;
6063
}
64+
65+
6166
}

0 commit comments

Comments
 (0)