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.
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
一种爬行字符串，就是说假如把一个字符串当做一个二叉树的根，然后它的非空子字符串是它的子节点，然后交换某个子字符串的两个子节点，重新爬行回去形成一个新的字符串，这个新字符串和原来的字符串互为爬行字符串。
解法1: 递归Recursion
解法2: 动态规划Dynamic Programming
Java:
public class Solution {
public boolean isScramble(String s1, String s2) {
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']--;
}
for (int i=0; i<26; i++) if (letters[i]!=0) return false;
for (int i=1; i<s1.length(); i++) {
if (isScramble(s1.substring(0,i), s2.substring(0,i))
&& isScramble(s1.substring(i), s2.substring(i))) return true;
if (isScramble(s1.substring(0,i), s2.substring(s2.length()-i))
&& isScramble(s1.substring(i), s2.substring(0,s2.length()-i))) return true;
}
return false;
}
}
Python:
# Time: O(n^4)
# Space: O(n^3)
class Solution(object):
# @return a boolean
def isScramble(self, s1, s2):
if not s1 or not s2 or len(s1) != len(s2):
return False
if s1 == s2:
return True
result = [[[False for j in xrange(len(s2))] for i in xrange(len(s1))] for n in xrange(len(s1) + 1)]
for i in xrange(len(s1)):
for j in xrange(len(s2)):
if s1[i] == s2[j]:
result[1][i][j] = True for n in xrange(2, len(s1) + 1):
for i in xrange(len(s1) - n + 1):
for j in xrange(len(s2) - n + 1):
for k in xrange(1, n):
if result[k][i][j] and result[n - k][i + k][j + k] or\
result[k][i][j + n - k] and result[n - k][i + k][j]:
result[n][i][j] = True
break return result[n][0][0]
C++: Recursion
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1==s2)
return true;
int len = s1.length();
int count[26] = {0};
for(int i=0; i<len; i++)
{
count[s1[i]-'a']++;
count[s2[i]-'a']--;
}
for(int i=0; i<26; i++)
{
if(count[i]!=0)
return false;
}
for(int i=1; i<=len-1; i++)
{
if( isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
return true;
if( isScramble(s1.substr(0,i), s2.substr(len-i)) && isScramble(s1.substr(i), s2.substr(0,len-i)))
return true;
}
return false;
}
};
C++: Recursion
class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1.size() != s2.size()) return false;
if (s1 == s2) return true;
string str1 = s1, str2 = s2;
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
if (str1 != str2) return false;
for (int i = 1; i < s1.size(); ++i) {
string s11 = s1.substr(0, i);
string s12 = s1.substr(i);
string s21 = s2.substr(0, i);
string s22 = s2.substr(i);
if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
s21 = s2.substr(s1.size() - i);
s22 = s2.substr(0, s1.size() - i);
if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
}
return false;
}
};
C++: DP
class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1.size() != s2.size()) return false;
if (s1 == s2) return true;
int n = s1.size();
vector<vector<vector<bool> > > dp (n, vector<vector<bool> >(n, vector<bool>(n + 1, false)));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dp[i][j][1] = s1[i] == s2[j];
}
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
for (int j = 0; j <= n - len; ++j) {
for (int k = 1; k < len; ++k) {
if ((dp[i][j][k] && dp[i + k][j + k][len - k]) || (dp[i + k][j][len - k] && dp[i][j + len - k][k])) {
dp[i][j][len] = true;
}
}
}
}
}
return dp[0][0][n];
}
};
C++:
class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1.size() != s2.size()) return false;
if (s1 == s2) return true;
int n = s1.size();
vector<vector<vector<bool> > > dp (n, vector<vector<bool> >(n, vector<bool>(n + 1, false)));
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
for (int k = 1; k <= n - max(i, j); ++k) {
if (s1.substr(i, k) == s2.substr(j, k)) {
dp[i][j][k] = true;
} else {
for (int t = 1; t < k; ++t) {
if ((dp[i][j][t] && dp[i + t][j + t][k - t]) || (dp[i][j + k - t][t] && dp[i + t][j][k - t])) {
dp[i][j][k] = true;
break;
}
}
}
}
}
}
return dp[0][0][n];
}
};