LeetCode.87.扰乱字符串（困难）

题目

LeetCode.87.扰乱字符串（困难）

使用下面描述的算法可以扰乱字符串 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 。

题解

题目描述已经给出了拆解步骤和子问题的划分。

思路

从最后一步开始想：

• 设s1拆解为a1和a2，s2拆解为b1和b2
• 因拆解后子串顺序有两种，如果s1能扰乱为s2，那么s1和s2对应关系也就有两种：
  • a1是否能从b1扰乱来，并且，a2是否能从b2扰乱来；其中a1.length == b1.length && a2.length == b2.length。
  • a1是否能从b2扰乱来，并且，a2是否能从b1扰乱来；其中a1.length == b2.length && a2.length == b1.length。

子问题和拆解步骤就出来了。

应该怎么拆解字符串？

穷举所有可以拆解的位置

有哪些状态？

• 拆解字符串需要知道起始索引和结束索引。
• 有两个字符串，也就有4个状态。
• 但是拆解过后的子串长度是相等的，所以可以不记录两个结束索引，只记录拆解的子串长度，缩减为3个状态。

边界条件

• 如果两个字符串长度不相等，两者无法通过扰乱变为一致。
• 如果两个字符串长度相等，但每种字符个数不相等，两者无法通过扰乱变为一致。
• 拆到只有一个字符的时候，直接判断字符是否相同。

递归解法

class Solution {
    fun isScramble(s1: String, s2: String): Boolean {
        if (s1.length != s2.length) return false
        if (s1 == s2) return true

        val s1CharCountMap = s1.groupingBy{it}.eachCount()
        val s2CharCountMap = s2.groupingBy{it}.eachCount()
        if (s1CharCountMap != s2CharCountMap) return false

        val n = s1.length
        for (i in 0 until n) {
            val a1 = s1.substring(0, i + 1)
            val a2 = s1.substring(i + 1, n)
            val b1 = s2.substring(0, i + 1)
            val b2 = s2.substring(i + 1, n)
            if (isScramble(a1, b1) && isScramble(a2, b2)) return true
            if (isScramble(a1, b2) && isScramble(a2, b1)) return true
        }
        return false
    }
}

时间复杂度指数级别

指针递归

上面的递归解法非常直白，但是不方便存储中间计算结果，子串改成指针形式。

class Solution {
    fun isScramble(s1: String, s2: String): Boolean {
        if (s1.length != s2.length) return false
        val n = s1.length

        // s1[i1, i1 + length - 1]和s2[i2, i2 + length - 1]是否有一样的字符和字符个数
        fun hasSameChars(i1: Int, i2: Int, length: Int): Boolean {
            val counts = IntArray(26) { 0 }
            for (j in i1 until i1 + length) {
                val index = s1[j].toInt() - 'a'.toInt()
                counts[index]++
            }
            for (j in i2 until i2 + length) {
                val index = s2[j].toInt() - 'a'.toInt()
                counts[index]--
            }
            return counts.sum() == 0
        }

        fun test(i1: Int, i2: Int, length: Int): Boolean {
            if (length == 1) return s1[i1] == s2[i2]

            // 词频不一样，肯定不能转换
            if (!hasSameChars(i1, i2, length)) return false

            // k为s1和s2分割出来的左半部分的长度
            // 左子串最短长度为1
            // 左子串最长长度为length - 1，因为要留一个长度给右子串
            for (k in 1 until length) {
                if (test(i1, i2, k) && test(i1 + k, i2 + k, length - k)) return true
                if (test(i1, i2 + length - k, k) && test(i1 + k, i2, length - k)) return true
            }
            return false
        }

        return test(0, 0, n) 
    }
}

记忆化递归

暴力递归有重叠子问题，需要记录中间计算状态。

class Solution {
    fun isScramble(s1: String, s2: String): Boolean {
        if (s1.length != s2.length) return false
        val n = s1.length

        // s1[i1, i1 + length - 1]和s2[i2, i2 + length - 1]是否有一样的字符和字符个数
        fun hasSameChars(i1: Int, i2: Int, length: Int): Boolean {
            val counts = IntArray(26) { 0 }
            for (j in i1 until i1 + length) {
                val index = s1[j].toInt() - 'a'.toInt()
                counts[index]++
            }
            for (j in i2 until i2 + length) {
                val index = s2[j].toInt() - 'a'.toInt()
                counts[index]--
            }
            return counts.sum() == 0
        }

        val memo = Array(n) { Array(n) { IntArray(n + 1) { -1 } } }

        fun test(i1: Int, i2: Int, length: Int): Boolean {
            if (memo[i1][i2][length] != -1) return memo[i1][i2][length] == 1

            if (length == 1) {
                val matched = s1[i1] == s2[i2]
                memo[i1][i2][length] = if (matched) 1 else 0
                return matched
            }

            // 词频不一样，肯定不能转换
            if (!hasSameChars(i1, i2, length)) return false

            // k为s1和s2分割出来的左半部分的长度
            // 左子串最短长度为1
            // 左子串最长长度为length - 1，因为要留一个长度给右子串
            for (k in 1 until length) {
                if (test(i1, i2, k) && test(i1 + k, i2 + k, length - k)) {
                    memo[i1][i2][length] = 1
                    return true
                }
                if (test(i1, i2 + length - k, k) && test(i1 + k, i2, length - k)) {
                    memo[i1][i2][length] = 1
                    return true
                }
            }
            memo[i1][i2][length] = 0
            return false
        }

        return test(0, 0, n) 
    }
}

时间复杂度O(n^4)

• 递归会枚举所有length的取值情况，1 <= length <= n。
• 对于每个length枚举了左子串字符数k的所有取值可能，1 <= k <= length。
• 递归枚举了所有i1的取值情况，0 <= i1 <= n - 1
• 递归枚举了所有i2的取值情况，0 <= i2 <= n - 1

空间复杂度O(n^3)

状态存储是三维数组。

自底向上的动态规划

记忆化递归的备忘录数组的填充过程已经给出了状态转移方程。

设dp[i][j][len]代表 s1 从 i 开始，s2 从 j 开始，后面长度为 len 的字符是否能形成扰乱字符串。

状态转移方程

设s1的左子串的长度为k。

dp[i][j][len] = dp[i][j][k] && dp[i + k][j + k][len - k] || dp[i][j + len - k][k] && dp[i + k][j][len - k]

边界情况

长度为1时，只需要判断字符是否相同。

class Solution {
    fun isScramble(s1: String, s2: String): Boolean {
        if (s1.length != s2.length) return false
        val n = s1.length
        val dp = Array(n) { Array(n) { BooleanArray(n + 1) { false } } }
        for (i in 0 until n) {
            for (j in 0 until n) {
                dp[i][j][1] = s1[i] == s2[j]
            }
        }
        for (len in 2..n) {
            for (i in 0..(n - len)) {
                for (j in 0..(n - len)) {
                    for (k in 1 until len) {
                        if (dp[i][j][k] && dp[i + k][j + k][len - k] || dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
                            dp[i][j][len] = true
                            break
                        }
                    }
                }
            }
        }
        return dp[0][0][n]
    }
}