目录

LeetCode87. 扰乱字符串

87. 扰乱字符串

Difficulty: 困难

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

  1. 如果字符串的长度为 1 ,算法停止
  2. 如果字符串的长度 > 1 ,执行下述步骤:
    • 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符串 xy ,且满足 s = x + y
    • 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,s 可能是 s = x + y 或者 s = y + x
    • xy 这两个子字符串上继续从步骤 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];
    }
}