LeetCode87. 扰乱字符串

2021-04-16 约 1477 字预计阅读 3 分钟

87. 扰乱字符串

Difficulty: 困难

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
- 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
- 随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
- 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1和 s2，判断 s2是否是 s1的扰乱字符串。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

示例 2：

输入：s1 = "abcde", s2 = "caebd"
输出：false

示例 3：

输入：s1 = "a", s2 = "a"
输出：true

提示：

$\text{s1.length = s2.length}$
$1 \leq \text{s1.length} \leq 30$
$s_1$ 和 $s_2$ 由小写英文字母组成

解法一

LeetCode4.16 每日一题，挺有意思记录一下

记忆化搜索，一开始没看题解磨了好一会儿磨出来的，没经过优化，50ms 过了

class Solution {

    char[] c1, c2;
    
    Boolean[][][][] dp = null;

    public boolean isScramble(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        dp = new Boolean[m+1][m+1][n+1][n+1];
        c1 = s1.toCharArray();
        c2 = s2.toCharArray();
        if (!check(0, m-1, 0, n-1)) return false;
        return dfs(0, m-1, 0, n-1);
    }

    public boolean dfs(int i1, int j1, int i2, int j2) {
        if (!check(i1, j1, i2, j2)) {
            return dp[i1][j1][i2][j2] = false;
        }
        if (i1 == j1) {
            if (c1[i1] == c2[i2]) {
                return true;
            }
            return false;
        }
        if (new String(c1, i1, j1-i1+1).equals(new String(c2, i2, j1-i1+1))) {
            // System.out.println(new String(c1, i1, j1-i1+1));
            return true;
        }
        if (dp[i1][j1][i2][j2] != null) {
            return dp[i1][j1][i2][j2];
        }
        int k = i1, p = i2;
        while (k < j1 && p < j2) {
            if (dfs(i1, k, i2, p) && dfs(k+1, j1, p+1, j2)) {
                dp[i1][k][i2][p] = true;
                dp[k+1][j1][p+1][j2] = true;
                return true;
            }
            k++; p++;
        }
        k = i1; p = j2;
        while (k < j1 && p > 0) {
            if (dfs(i1, k, p, j2) && dfs(k+1, j1, i2, p-1)) {
                dp[i1][k][p][j2] = true;
                dp[k+1][j1][i2][p-1] = true;
                return true;
            }
            k++; p--;
        }
        return dp[i1][j1][i2][j2] = false;
    }

    public boolean check(int i1, int j1, int i2, int j2) {
        if (j1-i1 != j2-i2) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        while (i1 <= j1 && i2 <= j2) {
            cnt1[c1[i1++]-'a']++;
            cnt2[c2[i2++]-'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] != cnt2[i]) {
                return false;
            }
        }
        return true;
    }
}

优化后的写法，一开始设置了四维状态 $i_1,j_1,i_2,j_2$ ，然后发现其实两个子串长度必须相同，所以可以直接用一个 $len$ 省掉一维状态，然后直接搜索就行了，最后再加上记忆化就能 AC 了，其实还是挺好写的

class Solution {

    char[] c1, c2;
    
    Boolean [][][] dp = null;

    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        dp = new Boolean[n+1][n+1][n+1];
        c1 = s1.toCharArray(); c2 = s2.toCharArray();
        return dfs(0, 0, n);
    }

    public boolean dfs(int i1, int i2, int len) {
        if (!check(i1, i2, len)) {
            return dp[i1][i2][len] = false;
        }
        if (len == 1) {
            return dp[i1][i2][len] = c1[i1] == c2[i2];
        }
        if (new String(c1, i1, len).equals(new String(c2, i2, len))) {
            return dp[i1][i2][len] = true;
        }
        if (dp[i1][i2][len] != null) {
            return dp[i1][i2][len];
        }
        int k = i1, p = i2;
        int j1 = i1+len-1, j2 = i2+len-1;
        while (k < j1 && p < j2) {
            // j1-k+k-i1+1
            if (dfs(i1, i2, k-i1+1) && dfs(k+1, p+1, j1-k)) {
                return dp[i1][i2][len] = true;
            }
            if (dfs(i1, j2-(k-i1+1)+1, k-i1+1) && dfs(k+1, i2, j1-k)) {
                return dp[i1][i2][len] = true;
            }
            k++; p++;
        }
        return dp[i1][i2][len] = false;
    }

    public boolean check(int i1, int i2, int len) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        int j1 = i1+len-1, j2 = i2+len-1;
        while (i1 <= j1 && i2 <= j2) {
            cnt1[c1[i1++]-'a']++;
            cnt2[c2[i2++]-'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] != cnt2[i]) {
                return false;
            }
        }
        return true;
    }
}

解法二

区间 DP 的写法，其实在前面写记忆化搜索的时候就意识到了这是个区间 DP，所以写完搜索后马上就写出了下面的解法。状态 $dp[i][j][len]$ 表示，子串 $s_1[i,i+len-1]$ 和 $s_2[j,j+len-1]$ 是否互为扰乱字符串

入口： $dp[i][j][1]=\text{True if } s_i = s_j$
转移：$dp[i][j][len] = \begin{cases} dp[i][j][k] \ \ \And \ \ dp[i+k][j+k][len-k] \\ dp[i][j+len-k][k] \ \ \And \ \ dp[i+k][j][len-k] \end{cases}(or)$
出口： $dp[0][0][n]$

class Solution {

    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        char[] c1 = s1.toCharArray(), c2 = s2.toCharArray();
        boolean[][][] dp = new boolean[n+1][n+1][n+1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = c1[i] == c2[j];
            }
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i+len-1 < n; i++) {
                for (int j = 0; j+len-1 < n; j++) {
                    for (int k = 1; k < len; k++) {
                        if (dp[i][j][len]) break;
                        boolean a = dp[i][j][k] & dp[i+k][j+k][len-k];
                        // j+len-1 - k + 1
                        boolean b = dp[i][j+len-1-k+1][k] & dp[i+k][j][len-k];
                        dp[i][j][len] = a | b;
                    }
                }
            }
        }
        return dp[0][0][n];
    }
}

目录

LeetCode87. 扰乱字符串

87. 扰乱字符串

解法一

解法二