/** * Scramble string, for two strings, say str1 = “tiger” and str2 = “itreg” *
* Scramble string, for two strings, say str1 = “tiger” and str2 = “itreg” * tiger * / \ * ti ger * / \ / \ * t i g er * / \ * e r * * itreg * / \ * it reg * / \ / \ * t i g re * / \ * e r * * In above case, since s1 can be generated from str2, that is, str1 can be generated from the partition tree, * which has the same leaf of str2, but the order of its child can be switched. * So str1 is said to be a scramble string of str2. * * A counter example is that Tiger and Tgrie are not scramble string of each other * * The principle of this approach goes as following * 1) Given two strings A and B, try to split each of them into two sub-strings sA1,sA2,sB1, * sB2 where sA1 and sB1 are anagrams and sA2 and sB2 are anagrams. * 2) If sA1 and sB1 are the scramble strings while sA2 and sBs are scramble strings, * then A and B should be scramble strings. * 3) Recursively analyze sA1 and sB1, sA2 and sB2 by start over from step 1). * * In previous example * * str1 = aabbbaccd, str2: aabcdbcba, * * They are split as: (aab)(bbaccd), (aab)(cdbcba) => compare bbaccd and cdbcba * They are split as: (bbac)(cd), (cd)(bcba) => compare bbac and bcba * They are split as: (b)(bac), b(cba) => (ba)(c) vs (c)(ba) */ public class ScrambleString { public static void main(String[] args) { // they are anagram as a whole string, but not scramble String s1 = "tiger"; String s2 = "tgrie"; System.out.println(isScrambleStringRecursive(s1, s2)); // they are anagram as well as scramble s1 = "tiger"; s2 = "itreg"; System.out.println(isScrambleStringRecursive(s1, s2)); } public static boolean isScrambleStringRecursive(String s1, String s2) { if (s1.length() != s2.length()) return false; if (s1.equals(s2)) return true; else { for (int i = 0; i < s1.length() - 1; i++) { String s1a = s1.substring(0, i + 1); String s1b = s1.substring(i + 1); String s2a = s2.substring(0, i + 1); String s2b = s2.substring(i + 1); String s2ar = s2.substring(s2.length() - 1 - i); String s2br = s2.substring(0, s2.length() - 1 - i); if ((isScrambleStringRecursive(s1a, s2a) && isScrambleStringRecursive(s1b, s2b)) || (isScrambleStringRecursive(s1a, s2ar) && isScrambleStringRecursive(s1b, s2br))) { return true; } } return false; } } }