Scramble String Problem Solution

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

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);
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment