Scramble String

This page explains Java solution to problem Scramble String using Dynamic programming algorithm.

Problem Statement

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:
  • 2.1. Split the string into 2 non-empty substrings at a random index, i.e. if the string is s, divide it to x and y where s = x + y.
  • 2.2. 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.
  • 2.3. 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.

Input: s1 = "great", s2 = "rgeat"
Output: true

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

Solution

package com.vc.hard;

class ScrambleString {
    private int m;
    private 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];

        dp[l1][l2][r1 - l1] = false;
        //s1 = great s2 = rgeat
        for(int i = 0; i + l1 <= r1; i++) {
            dp[l1][l2][r1 - l1] = dp[l1][l2][r1 - l1] ||
                    //Check for length i
                    dfs(
                            s1, s2,
                            l1, l1 + i,                                 //g
                            l2, l2 + i                                  //r
                    ) &&
                            dfs(
                                    s1, s2,
                                    l1 + i + 1, r1,                     //reat
                                    l2 + i + 1, r2                      //geat
                            ) ||

                    //Check for length i, this time s2 in reverse
                    dfs(
                            s1, s2,
                            l1, l1 + i,                                 //g
                            r2 - i, r2                                  //t
                    ) &&
                            dfs(
                                    s1, s2,
                                    l1 + i + 1, r1,                     //reat
                                    l2, l2 + (r1 - l1 - i - 1)          //rgea
                            );

            if(dp[l1][l2][r1 - l1]) return true;
        }
        return dp[l1][l2][r1 - l1];
    }
}

Time Complexity

O(N!) Where
N is length of input string s1 or s2(Both will have same length)

Space Complexity

O(N³) Where
N is length of input string s1 or s2(Both will have same length)