LeetCode 87: Scramble String Solution

Master LeetCode problem 87 (Scramble String), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

87. Scramble String

Hard

String Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use a recursive approach with memoization to check if two strings are scrambled versions of each other. We can try all possible splits to divide the strings into two parts and check if the corresponding parts are scrambled strings. We can use a 3D memoization array to store the results of subproblems.

Algorithm:

Check if the lengths of the two strings are equal. If not, return false.
Check if the strings are equal. If yes, return true.
Check if the characters in the two strings are the same. If not, return false.
Iterate through all possible splits of the strings and check if at least one split leads to scrambled strings.
Use memoization to store the results of subproblems to avoid redundant calculations.

Time Complexity:

The time complexity of this approach is O(n^4) where n is the length of the strings.

Space Complexity:

The space complexity of this approach is O(n^3) for the memoization array.

Solution Code

class Solution {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        if (n != s2.length()) return false;
        
        boolean[][][] memo = new boolean[n][n][n + 1];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j][1] = s1.charAt(i) == s2.charAt(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 ((memo[i][j][k] && memo[i + k][j + k][len - k]) ||
                            (memo[i][j + len - k][k] && memo[i + k][j][len - k])) {
                            memo[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        
        return memo[0][0][n];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 87 (Scramble String)?

This page provides optimized solutions for LeetCode problem 87 (Scramble String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 87 (Scramble String)?

The time complexity for LeetCode 87 (Scramble String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 87 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 87 in Java, C++, or Python.

Back to LeetCode Solutions