Leetcode Scramble String problem solution

YASH PAL,

In this Leetcode Scramble String problem solution We can scramble a string s to get a string t using the following algorithm:

  1. If the length of the string is 1, stop.
  2. If the length of the string is > 1, do the following:
  3. Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
  4. Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
  5. Apply step 1 recursively on each of the two substrings x and y.

Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.

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

coding problems