Scramble String Problem: Given two strings s1
and s2
of the same length, return true
if s2
is a scrambled string of s1
, otherwise, return false
.
Input: s1 = "abcde", s2 = "caebd" Output: false
Table of Contents
Scramble String Problem Solution
Problem Solution In Python
def isScramble(self, s1: str, s2: str) -> bool:
def split(l1, r1, l2, r2):
if r1 - l1 == 1:
return s1[l1] == s2[l2]
if sorted(s1[l1:r1]) != sorted(s2[l2:r2]):
return False
for i in range(1, r1-l1):
if split(l1, l1+i, l2, l2+i) and split(l1+i, r1, l2+i, r2) or \
split(l1, l1+i, r2-i, r2) and split(l1+i, r1, l2, r2-i):
return True
return split(0, len(s1), 0, len(s2))
Problem Solution In Java
class Solution {
int m;
Boolean[][][] dp;
public boolean isScramble(String s1, String s2) {
m = s1.length();
dp = new Boolean[m][m][m];
return dfs(s1, s2, 0,m-1, 0, m-1);
}
private boolean dfs(String s1, String s2, int l1, int r1, int l2, int r2) {
if (l1 == r1) {
return s1.charAt(l1) == s2.charAt(l2);
}
if (dp[l1][l2][r1-l1] != null) return dp[l1][l2][r1-l1];
if (s1.substring(l1,r1+1).equals(s2.substring(l2, r2+1))) {
dp[l1][l2][r1-l1] = true;
return true;
}
dp[l1][l2][r1-l1] = false;
for (int i = 0; i < r1 - l1; i++) {
int left1 = l1 + i, left2 = l2 + i;
int right1 = r2 - i, right2 = l2 + r1 - l1 - i - 1;
dp[l1][l2][r1-l1] = dp[l1][l2][r1-l1] ||
(dfs(s1,s2,l1,left1,l2,left2) && dfs(s1,s2,left1+1,r1,left2+1,r2)) ||
(dfs(s1,s2,l1,left1,right1,r2) && dfs(s1,s2,left1+1,r1,l2,right2));
if (dp[l1][l2][r1-l1]) break;
}
return dp[l1][l2][r1-l1];
}
}
Problem Solution In C++
class Solution {
public:
bool isScramble(string s1, string s2) {
int sSize = s1.size(), len, i, j, k;
if(0==sSize) return true;
if(1==sSize) return s1==s2;
bool isS[sSize+1][sSize][sSize];
for(i=0; i<sSize; ++i)
for(j=0; j<sSize; ++j)
isS[1][i][j] = s1[i] == s2[j];
for(len=2; len <=sSize; ++len)
for(i=0; i<=sSize-len; ++i)
for(j=0; j<=sSize-len; ++j)
{
isS[len][i][j] = false;
for(k=1; k<len && !isS[len][i][j]; ++k)
{
isS[len][i][j] = isS[len][i][j] || (isS[k][i][j] && isS[len-k][i+k][j+k]);
isS[len][i][j] = isS[len][i][j] || (isS[k][i+len-k][j] && isS[len-k][i][j+k]);
}
}
return isS[sSize][0][0];
}
};
Problem Solution In C
bool checkscramble(char* s1, char* s2, int size) {
bool o1, o2;
int i, val1=0, val2=0, val3 =0, val4 =0;
if (size == 2 && ((s1[0] == s2[0] && s1[1] == s2[1]) || (s1[0] == s2[1] && s1[1] == s2[0]))) {
return true;
} else if (size == 2) {
return false;
}
if (size ==1 && s1[0] == s2[0]) {
return true;
} else if (size == 1) {
return false;
}
for (i =0;i<size;i++) {
val1 += s1[i];
val2 += s2[i];
val3 += s1[i] * (s1[i] & 2);
val4 += s2[i] * (s2[i] & 2);
}
if (val1 != val2 || val3 != val4) {
return false;
}
for (i=1; i < size; i++) {
o1=checkscramble( s1, s2, i);
o2=checkscramble( s1+i, s2+i, size-i);
if (o1 && o2)
return true;
o1=checkscramble( (s1+(size-i)), s2, i);
o2=checkscramble( s1, s2+i, size-i);
if (o1 && o2)
return true;
}
return false;
}
bool isScramble(char* s1, char* s2) {
int size = strlen(s1);
return checkscramble(s1, s2, size);
}