87. Scramble String

public class Solution {
    public bool IsScramble(string s1, string s2) {
        int n = s1.Length;
        bool[][][] dp = new bool[n + 1][][];
        for (int i = 0; i < dp.Length; i++) {
            dp[i] = new bool[n][];
            for (int j = 0; j < dp[i].Length; j++) {
                dp[i][j] = new bool[n];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[1][i][j] = s1[i] == s2[j];
            }
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i < n + 1 - length; i++) {
                for (int j = 0; j < n + 1 - length; j++) {
                    for (int newLength = 1; newLength < length; newLength++) {
                        bool[] dp1 = dp[newLength][i];
                        bool[] dp2 = dp[length - newLength][i + newLength];
                        dp[length][i][j] |= dp1[j] && dp2[j + newLength];
                        dp[length][i][j] |=
                            dp1[j + length - newLength] && dp2[j];
                    }
                }
            }
        }
        return dp[n][0][0];
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsScramble(string s1, string s2) {
        int n = s1.size();
        bool[][][] dp = new bool[n + 1][][];
        for (int i = 0; i < dp.size(); i++) {
            dp[i] = new bool[n][];
            for (int j = 0; j < dp[i].size(); j++) {
                dp[i][j] = new bool[n];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[1][i][j] = s1[i] == s2[j];
            }
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i < n + 1 - length; i++) {
                for (int j = 0; j < n + 1 - length; j++) {
                    for (int newLength = 1; newLength < length; newLength++) {
                        bool[] dp1 = dp[newLength][i];
                        bool[] dp2 = dp[length - newLength][i + newLength];
                        dp[length][i][j] |= dp1[j] && dp2[j + newLength];
                        dp[length][i][j] |=
                            dp1[j + length - newLength] && dp2[j];
                    }
                }
            }
        }
        return dp[n][0][0];
    }
}

class Solution {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        boolean dp[][][] = new boolean[n + 1][n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i < n + 1 - length; i++) {
                for (int j = 0; j < n + 1 - length; j++) {
                    for (int newLength = 1; newLength < length; newLength++) {
                        boolean dp1[] = dp[newLength][i];
                        boolean dp2[] = dp[length - newLength][i + newLength];
                        dp[length][i][j] |= dp1[j] && dp2[j + newLength];
                        dp[length][i][j] |=
                        dp1[j + length - newLength] && dp2[j];
                    }
                }
            }
        }
        return dp[n][0][0];
    }
}

var isScramble = function (s1, s2) {
    const n = s1.length;
    let dp = new Array(n + 1)
        .fill(0)
        .map(() => new Array(n).fill(0).map(() => new Array(n).fill(false)));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
        }
    }
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i < n + 1 - length; i++) {
            for (let j = 0; j < n + 1 - length; j++) {
                for (let newLength = 1; newLength < length; newLength++) {
                    const dp1 = dp[newLength][i];
                    const dp2 = dp[length - newLength][i + newLength];
                    dp[length][i][j] |= dp1[j] && dp2[j + newLength];
                    dp[length][i][j] |= dp1[j + length - newLength] && dp2[j];
                }
            }
        }
    }
    return dp[n][0][0];
};

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        dp = [
            [[False for j in range(n)] for i in range(n)] for l in range(n + 1)
        ]
        for i in range(n):
            for j in range(n):
                dp[1][i][j] = s1[i] == s2[j]
        for length in range(2, n + 1):
            for i in range(n + 1 - length):
                for j in range(n + 1 - length):
                    for new_length in range(1, length):
                        dp1 = dp[new_length][i]
                        dp2 = dp[length - new_length][i + new_length]
                        dp[length][i][j] |= dp1[j] and dp2[j + new_length]
                        dp[length][i][j] |= (
                            dp1[j + length - new_length] and dp2[j]
                        )
        return dp[n][0][0]

func isScramble(s1 string, s2 string) bool {
    n := len(s1)
    dp := make([][][]bool, n+1)
    for i := range dp {
        dp[i] = make([][]bool, n)
        for j := range dp[i] {
            dp[i][j] = make([]bool, n)
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            dp[1][i][j] = s1[i] == s2[j]
        }
    }
    for length := 2; length <= n; length++ {
        for i := 0; i < n+1-length; i++ {
            for j := 0; j < n+1-length; j++ {
                for newLength := 1; newLength < length; newLength++ {
                    dp1 := dp[newLength][i]
                    dp2 := dp[length-newLength][i+newLength]
                    dp[length][i][j] = dp[length][i][j] ||
                        (dp1[j] && dp2[j+newLength])
                    dp[length][i][j] = dp[length][i][j] ||
                        (dp1[j+length-newLength] && dp2[j])
                }
            }
        }
    }
    return dp[n][0][0]
}

Explanation

Algorithm

1. Если длина строки равна 1, остановиться.

2. Если длина строки больше 1, выполнить следующее:

- Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y.

- Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x.

- Применить шаг 1 рекурсивно к каждой из двух подстрок x и y.

Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false.

Пример:

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.

👨‍💻

Алгоритм:

1️⃣

- Итерируйте i от 0 до n-1.

- Итерируйте j от 0 до n-1.

- Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования).

2️⃣

- Итерируйте length от 2 до n.

- Итерируйте i от 0 до n + 1 - length.

- Итерируйте j от 0 до n + 1 - length.

3️⃣

- Итерируйте newLength от 1 до length - 1.

- Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true.

- Верните dp[n][0][0].

😎