Scramble String

Problem

We can scramble a string s to get a string t using the following algorithm:

If the length of the string is 1, stop.
If the length of the string is > 1, do the following:
- 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.
- 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.
- 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.

Examples

Example 1

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

Example 2

Input: s1 = "abcde", s2 = "caebd"
Output: false

Example 3

Input: s1 = "a", s2 = "a"
Output: true

Constraints

s1.length == s2.length
1 <= s1.length <= 30
s1 and s2 consist of lowercase English letters.

Solution

Method 1 - Top Down DP with Memoization

Intuition

Recursively check all possible splits of the strings. For each split, try both the non-swapped and swapped cases. Use memoization to avoid redundant computation. If the characters in the substrings do not match, prune early.

Approach

Define a recursive function that checks if s1[i:i+len] can be scrambled to s2[j:j+len]. For each possible split, check both the swapped and non-swapped cases. Use a cache to store results for subproblems.

Code

C++

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        unordered_map<string, bool> memo;
        function<bool(string, string)> dfs = [&](string a, string b) {
            string key = a + "#" + b;
            if (memo.count(key)) return memo[key];
            if (a == b) return memo[key] = true;
            if (a.size() != b.size() || string(a.begin(), a.end()) != string(b.begin(), b.end())) return memo[key] = false;
            string sa = a, sb = b;
            sort(sa.begin(), sa.end());
            sort(sb.begin(), sb.end());
            if (sa != sb) return memo[key] = false;
            int len = a.size();
            for (int i = 1; i < len; ++i) {
                if ((dfs(a.substr(0, i), b.substr(0, i)) && dfs(a.substr(i), b.substr(i))) ||
                    (dfs(a.substr(0, i), b.substr(len-i)) && dfs(a.substr(i), b.substr(0, len-i))))
                    return memo[key] = true;
            }
            return memo[key] = false;
        };
        return dfs(s1, s2);
    }
};

Go

func isScramble(s1 string, s2 string) bool {
    memo := make(map[string]bool)
    var dfs func(a, b string) bool
    dfs = func(a, b string) bool {
        key := a + "#" + b
        if v, ok := memo[key]; ok {
            return v
        }
        if a == b {
            memo[key] = true
            return true
        }
        if len(a) != len(b) {
            memo[key] = false
            return false
        }
        sa, sb := []byte(a), []byte(b)
        sort.Slice(sa, func(i, j int) bool { return sa[i] < sa[j] })
        sort.Slice(sb, func(i, j int) bool { return sb[i] < sb[j] })
        if string(sa) != string(sb) {
            memo[key] = false
            return false
        }
        n := len(a)
        for i := 1; i < n; i++ {
            if (dfs(a[:i], b[:i]) && dfs(a[i:], b[i:])) ||
               (dfs(a[:i], b[n-i:]) && dfs(a[i:], b[:n-i])) {
                memo[key] = true
                return true
            }
        }
        memo[key] = false
        return false
    }
    return dfs(s1, s2)
}

Java

public boolean isScramble(String s1, String s2) {
    Map<String, Boolean> memo = new HashMap<>();
    return dfs(s1, s2, memo);
}
private boolean dfs(String a, String b, Map<String, Boolean> memo) {
    String key = a + "#" + b;
    if (memo.containsKey(key)) return memo.get(key);
    if (a.equals(b)) return memo.put(key, true) == null ? true : true;
    if (a.length() != b.length()) return memo.put(key, false) == null ? false : false;
    char[] ca = a.toCharArray(), cb = b.toCharArray();
    Arrays.sort(ca); Arrays.sort(cb);
    if (!Arrays.equals(ca, cb)) return memo.put(key, false) == null ? false : false;
    int n = a.length();
    for (int i = 1; i < n; i++) {
        if ((dfs(a.substring(0, i), b.substring(0, i), memo) && dfs(a.substring(i), b.substring(i), memo)) ||
            (dfs(a.substring(0, i), b.substring(n-i), memo) && dfs(a.substring(i), b.substring(0, n-i), memo)))
            return memo.put(key, true) == null ? true : true;
    }
    return memo.put(key, false) == null ? false : false;
}

Kotlin

fun isScramble(s1: String, s2: String): Boolean {
    val memo = mutableMapOf<String, Boolean>()
    fun dfs(a: String, b: String): Boolean {
        val key = "$a#$b"
        memo[key]?.let { return it }
        if (a == b) return true.also { memo[key] = true }
        if (a.length != b.length) return false.also { memo[key] = false }
        if (a.toCharArray().sorted() != b.toCharArray().sorted()) return false.also { memo[key] = false }
        val n = a.length
        for (i in 1 until n) {
            if ((dfs(a.substring(0, i), b.substring(0, i)) && dfs(a.substring(i), b.substring(i))) ||
                (dfs(a.substring(0, i), b.substring(n-i)) && dfs(a.substring(i), b.substring(0, n-i))))
                return true.also { memo[key] = true }
        }
        return false.also { memo[key] = false }
    }
    return dfs(s1, s2)
}

Python

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dfs(a, b):
            if a == b:
                return True
            if len(a) != len(b):
                return False
            if sorted(a) != sorted(b):
                return False
            n = len(a)
            for i in range(1, n):
                if (dfs(a[:i], b[:i]) and dfs(a[i:], b[i:])) or \
                   (dfs(a[:i], b[-i:]) and dfs(a[i:], b[:-i])):
                    return True
            return False
        return dfs(s1, s2)

Rust

use std::collections::HashMap;
impl Solution {
    pub fn is_scramble(s1: String, s2: String) -> bool {
        fn dfs(a: &str, b: &str, memo: &mut HashMap<(String, String), bool>) -> bool {
            let key = (a.to_string(), b.to_string());
            if let Some(&v) = memo.get(&key) { return v; }
            if a == b { memo.insert(key, true); return true; }
            if a.len() != b.len() { memo.insert(key, false); return false; }
            let mut ca: Vec<char> = a.chars().collect();
            let mut cb: Vec<char> = b.chars().collect();
            ca.sort_unstable(); cb.sort_unstable();
            if ca != cb { memo.insert(key, false); return false; }
            let n = a.len();
            for i in 1..n {
                if (dfs(&a[..i], &b[..i], memo) && dfs(&a[i..], &b[i..], memo)) ||
                   (dfs(&a[..i], &b[n-i..], memo) && dfs(&a[i..], &b[..n-i], memo)) {
                    memo.insert(key, true); return true;
                }
            }
            memo.insert(key, false); false
        }
        let mut memo = HashMap::new();
        dfs(&s1, &s2, &mut memo)
    }
}

TypeScript

function isScramble(s1: string, s2: string): boolean {
    const memo = new Map<string, boolean>();
    function dfs(a: string, b: string): boolean {
        const key = `${a}#${b}`;
        if (memo.has(key)) return memo.get(key)!;
        if (a === b) return memo.set(key, true) && true;
        if (a.length !== b.length) return memo.set(key, false) && false;
        if ([...a].sort().join('') !== [...b].sort().join('')) return memo.set(key, false) && false;
        const n = a.length;
        for (let i = 1; i < n; i++) {
            if ((dfs(a.slice(0, i), b.slice(0, i)) && dfs(a.slice(i), b.slice(i))) ||
                (dfs(a.slice(0, i), b.slice(n-i)) && dfs(a.slice(i), b.slice(0, n-i))))
                return memo.set(key, true) && true;
        }
        return memo.set(key, false) && false;
    }
    return dfs(s1, s2);
}

Complexity

⏰ Time complexity: O(N^4), where N is the length of the string.
🧺 Space complexity: O(N^3), for the memoization table.

Method 2 - Bottom Up DP

Intuition

Convert the recursive solution to an iterative bottom-up DP. Use a 3D DP table where dp[i][j][len] is true if s1[i:i+len] can be scrambled to s2[j:j+len]. Build up the solution for all substring lengths.

Approach

Initialize a 3D DP table. For substrings of length 1, set dp[i][j][1] to true if s1[i] == s2[j]. For longer substrings, try all possible splits and check both swapped and non-swapped cases. Fill the table iteratively.

Code

C++

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        if (n != s2.size()) return false;
        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][j+len-k][k] && dp[i+k][j][len-k])) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
};

Go

func isScrambleBU(s1, s2 string) bool {
    n := len(s1)
    if n != len(s2) {
        return false
    }
    dp := make([][][]bool, n)
    for i := range dp {
        dp[i] = make([][]bool, n)
        for j := range dp[i] {
            dp[i][j] = make([]bool, n+1)
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            dp[i][j][1] = s1[i] == s2[j]
        }
    }
    for l := 2; l <= n; l++ {
        for i := 0; i <= n-l; i++ {
            for j := 0; j <= n-l; j++ {
                for k := 1; k < l; k++ {
                    if (dp[i][j][k] && dp[i+k][j+k][l-k]) ||
                       (dp[i][j+l-k][k] && dp[i+k][j][l-k]) {
                        dp[i][j][l] = true
                        break
                    }
                }
            }
        }
    }
    return dp[0][0][n]
}

Java

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

Kotlin

fun isScrambleBU(s1: String, s2: String): Boolean {
    val n = s1.length
    if (n != s2.length) return false
    val dp = Array(n) { Array(n) { BooleanArray(n+1) } }
    for (i in 0 until n)
        for (j in 0 until n)
            dp[i][j][1] = s1[i] == s2[j]
    for (len in 2..n) {
        for (i in 0..(n-len)) {
            for (j in 0..(n-len)) {
                for (k in 1 until len) {
                    if ((dp[i][j][k] && dp[i+k][j+k][len-k]) ||
                        (dp[i][j+len-k][k] && dp[i+k][j][len-k])) {
                        dp[i][j][len] = true
                        break
                    }
                }
            }
        }
    }
    return dp[0][0][n]
}

Python

class Solution:
    def isScrambleBU(self, s1: str, s2: str) -> bool:
        n = len(s1)
        if n != len(s2): return False
        dp = [[[False]*(n+1) for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                dp[i][j][1] = s1[i] == s2[j]
        for l in range(2, n+1):
            for i in range(n-l+1):
                for j in range(n-l+1):
                    for k in range(1, l):
                        if (dp[i][j][k] and dp[i+k][j+k][l-k]) or \
                           (dp[i][j+l-k][k] and dp[i+k][j][l-k]):
                            dp[i][j][l] = True
                            break
        return dp[0][0][n]

Rust

impl Solution {
    pub fn is_scramble_bu(s1: String, s2: String) -> bool {
        let n = s1.len();
        if n != s2.len() { return false; }
        let s1 = s1.as_bytes();
        let s2 = s2.as_bytes();
        let mut dp = vec![vec![vec![false; n+1]; n]; n];
        for i in 0..n {
            for j in 0..n {
                dp[i][j][1] = s1[i] == s2[j];
            }
        }
        for len in 2..=n {
            for i in 0..=n-len {
                for j in 0..=n-len {
                    for k in 1..len {
                        if (dp[i][j][k] && dp[i+k][j+k][len-k]) ||
                           (dp[i][j+len-k][k] && dp[i+k][j][len-k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        dp[0][0][n]
    }
}

TypeScript

function isScrambleBU(s1: string, s2: string): boolean {
    const n = s1.length;
    if (n !== s2.length) return false;
    const dp: boolean[][][] = Array.from({length: n}, () => Array.from({length: n}, () => Array(n+1).fill(false)));
    for (let i = 0; i < n; i++)
        for (let j = 0; j < n; j++)
            dp[i][j][1] = s1[i] === s2[j];
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n-len; i++) {
            for (let j = 0; j <= n-len; j++) {
                for (let k = 1; k < len; k++) {
                    if ((dp[i][j][k] && dp[i+k][j+k][len-k]) ||
                        (dp[i][j+len-k][k] && dp[i+k][j][len-k])) {
                        dp[i][j][len] = true;
                        break;
                    }
                }
            }
        }
    }
    return dp[0][0][n];
}

Complexity

⏰ Time complexity: O(N^4), where N is the length of the string.
🧺 Space complexity: O(N^3), for the DP table.

Problem

Examples

Example 1

Example 2

Example 3

Constraints

Solution

Method 1 - Top Down DP with Memoization

Intuition

Approach

Code

C++

Go

Java

Kotlin

Python

Rust

TypeScript

Complexity

Method 2 - Bottom Up DP

Intuition

Approach

Code

C++

Go

Java

Kotlin

Python

Rust

TypeScript

Complexity

Comments