LeetCode087——扰乱字符串

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/scramble-string/description/

题目描述：

知识点：动态规划

思路一：用动态规划求出所有的扰乱字符串（在LeetCode中提交会超时）

状态定义：

f(x, y)--------字符串s1[x, y]范围内字符串的扰乱字符串列表

状态转移：

（1）当x == y时，f(x, y) = s1.charAt(x)。

（2）当x != y时，f(x, y) = f(x, x)与f(x + 1, y)的组合 + f(x, x + 1)与f(x + 2, y)的组合 + ... + f(x, y - 1)与f(y, y)的组合。

时间复杂度极高，是O(n1 ^ 5)，其中n1位字符串s1的长度。空间复杂度是O(n1 ^ 3)。

JAVA代码：

public class Solution {

    public boolean isScramble(String s1, String s2) {
        int n1 = s1.length();
        List<String>[][] lists = new List[n1][n1];
        for (int i = 0; i < n1; i++) {
            lists[i][i] = new ArrayList<String>();
            lists[i][i].add(s1.substring(i, i + 1));
        }
        for (int gap = -1; gap >= 1 - n1; gap--) {
            for (int i = 0; i - gap <= n1 - 1; i++) {
                lists[i][i - gap] = new ArrayList<String>();
                for (int k = i; k <= i - gap - 1; k++) {
                    List<String> list1 = lists[i][k];
                    List<String> list2 = lists[k + 1][i - gap];
                    for(String string1 : list1){
                        for(String string2 : list2){
                            if(!lists[i][i - gap].contains(string1 + string2)) {
                                lists[i][i - gap].add(string1 + string2);
                            }
                            if(!lists[i][i - gap].contains(string2 + string1)) {
                                lists[i][i - gap].add(string2 + string1);
                            }
                        }
                    }
                }
            }
        }
        if(lists[0][n1 - 1].contains(s2)){
            return true;
        }
        return false;
    }
}

思路二：动态规划2

在思路一的动态规划中，我们求出了字符串s1的所有扰乱字符串，并且还求出了字符串s1的任意连续子串的扰乱字符串，这其实多求了很多多余的信息。我们修改我们的状态定义。

状态定义：

f(x, y, z)--------s1中x位置开始的长度为z的字符串能否与s2中y位置开始的长度为z的字符串相匹配

状态转移：

f(x, y, z) |= f(x, y, k) && f(x + k, y + k, z - k) || f(x, y + z - k, k) && f(x + k, y, z - k)

上式相当于把s1中x位置开始的长度为z的字符串分为左右两部分，把s2中y位置开始的长度为z的字符串也分成左右两部分。那么该怎么分呢？一个k值对应一种分法。k值介于1 ~ z - 1之间。

我们判断s1的左子串能否与s2的左子串相匹配，且s1的右子串能否与s2的右子串相匹配。或者s1的左子串能否与s2的右子串相匹配，且s1的右子串能否与s2的左子串相匹配。一旦有一个k值使其匹配了，我们就可以令f(x, y, z) = true，并break跳出一层循环。

时间复杂度是O(n1 ^ 4)，空间复杂度是O(n1 ^ 3)。

JAVA代码：

public class Solution {

    public boolean isScramble(String s1, String s2) {
        int n1 = s1.length();
        int n2 = s2.length();
        if(n1 != n2){
            return false;
        }
        boolean[][][] flag = new boolean[n1][n1][n1 + 1];
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n1; j++) {
                flag[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int len = 2; len <= n1; len++) {
            for (int i = 0; i < n1 - len + 1; i++) {
                for (int j = 0; j < n1 - len + 1; j++) {
                    for (int k = 1; k < len; k++) {
                        if(flag[i][j][len]){
                            continue;
                        }
                        if((flag[i][j][k] && flag[i + k][j + k][len - k]) || (flag[i][j + len - k][k] && flag[i + k][j][len - k])){
                            flag[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return flag[0][0][n1];
    }
}

LeetCode解题报告：