Scramble String
題意：
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":
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".
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".
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.
解題思路：
以下四種解法參考網友 Yu Zhang 的解題思路
暴力法：
基本的思想就是：在S1上找到一個切割點，左邊長度為i, 右邊長為len - i。
有2種情況表明它們是IsScramble
- S1的左邊和S2的左邊是IsScramble， S1的右邊和S2的右邊是IsScramble
- S1的左邊和S2的右邊是IsScramble， S1的右邊和S2的左邊是IsScramble （實際上是交換了S1的左右子樹）
其複雜度約 $$O(3^{n})$$，以下引自網友 stellari對複雜度的解釋：
看了你的不少文章，感覺收穫良多！只是有點小問題想請教：按照我的理解，那個遞歸算法在最差情況下應該是O(3^n)，而非O(n^2)。理由是：假設函數運行時間為f(n)，那麼由於在每次函數調用中都要考慮1~n之間的所有長度，並且正反都要檢查，所以有 f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)]. 易推得f(n+1) = 3(fn), 故f(n) = O(3^n)。當然這是最差情況下的時間複雜度。那麼你提到的O(n^2)，是否是通過其他數學方法得到的更tight的上限？歡迎探討！
複雜度太高，可透過lintcode但無法通過leetcode！
public class Solution {
/**
* @param s1 A string
* @param s2 Another string
* @return whether s2 is a scrambled string of s1
*/
public boolean isScramble(String s1, String s2) {
if (s1 == null && s2 == null) {
return true;
}
if (s1.length() != s2.length()) {
return false;
}
return helper(s1, s2);
}
public boolean helper(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
if (s1.length() == 1) {
return s1.equals(s2);
}
int len = s1.length();
for (int i = 1; i < s1.length(); i++) {
// 檢查 S1的左邊是否和S2的左邊是IsScramble， S1的右邊是否和S2的右邊是IsScramble
if (helper(s1.substring(0, i), s2.substring(0, i))
&& helper(s1.substring(i, len), s2.substring(i, len))) {
return true;
}
// 檢查 S1 的左邊是否和 S2 的右邊是 IsScramble ， S1的右邊是否和 S2 的左邊是 IsScramble
if (helper(s1.substring(0, i), s2.substring(len - i, len))
&& helper(s1.substring(i, len), s2.substring(0, len - i))) {
return true;
}
}
return false;
}
}
解法二：遞迴法加減枝
來避免掉不必要的遞迴，在作遞迴前，先將兩個字串作排序，若有不同的字元則直接返回 false ，否則繼續往下檢查，可通過leetcode，但面試官應該不夠滿意。
private boolean helper(String s1, String s2) {
if (s1.length() == 1) {
return s1.equals(s2);
}
char[] s1Char = s1.toCharArray();
Arrays.sort(s1Char);
char[] s2Char = s2.toCharArray();
Arrays.sort(s2Char);
for (int i = 0; i < s1Char.length; i++) {
if (s1Char[i] != s2Char[i]) {
return false;
}
}
int len = s1.length();
for (int i = 1; i < len; i++) {
if (helper(s1.substring(0, i), s2.substring(0, i))
&& helper(s1.substring(i, len), s2.substring(i, len))) {
return true;
}
if (helper(s1.substring(0, i), s2.substring(len - i, len))
&& helper(s1.substring(i, len), s2.substring(0, len - i))) {
return true;
}
}
return false;
}
解法三：加上記憶矩陣
我們在遞歸中加上記憶矩陣，也可以減少重複運算，但是我們現在就改一下之前遞歸的結構以方便加上記憶矩陣，我們用index1記憶S1起始地址，index2記憶S2起始地址，len 表示字符串的長度。這樣我們可以用一個三維數組來記錄計算過的值，同樣可以通過leetcode的檢查。這個三維數組一個是$$O(N^{3})$$的複雜度，在每一個遞歸中，要從1-len地計算一次所有的子串，所以一共的複雜度是N^4
因我們並未對原本的字串作任何改變，因此我們使用起始點(index1, index2) 加上長度 (len) 來幫助我們處用子字串的部份。
public class Solution {
public boolean isScramble(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() != s2.length()) {
return false;
}
int len = s1.length();
int[][][] mem = new int[len][len][len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
for (int k = 0; k < len; k++) {
mem[i][j][k] = -1;
}
}
}
return helper(s1, 0, s2, 0, len, mem);
}
private boolean helper(String s1, int index1, String s2, int index2, int len, int[][][] mem) {
if (s1.length() == 1) {
// 不能直接用 equals，因為我們沒有對原本的字串作任何改變。
return s1.charAt(index1) == s2.charAt(index2);
}
int res = mem[index1][index2][len - 1];
if (res != -1) {
return (res == 1) ? true : false;
}
res = 0;
for (int i = 1; i < len; i++) {
if (helper(s1, index1, s2, index2, i, mem) && helper(s1, index1 + i, s2, index2 + i, len - i, mem)) {
res = 1;
break;
}
if (helper(s1, index1, s2, index2 + len - i, i, mem) && helper(s1, index1 + i, s2, index2, len - i, mem)) {
res = 1;
break;
}
}
mem[index1][index2][len - 1] = res;
return (res == 1) ? true : false;
}
}