# 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`.

Example 1:

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

Example 2:

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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(N3) Where
N is length of input string s1 or s2(Both will have same length)