Ricky.L的随笔
0%

LeetCode.132.分割回文串 II（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.132.分割回文串 II（困难）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

提示：

  • 1 <= s.length <= 2000
  • s 仅由小写英文字母组成

题解

拆解问题

如果已经求得一个子串的最少分割次数，是可以推导出整个串的最少分割次数。

  • 要保证分割次数最少，先检查整个串s是不是回文。
    • 如果是，就不用分割了，分割次数是0。
    • 如果s不是回文，需要在0到n - 1（n为s长度）中找一个分割位置i。
      • 如果s[0: i]的最少分割次数已经知道（0 <= i < n），同时s[i + 1:]是回文，说明在s[0: i]的最少分割次数基础上还要再多分割一次才能完成整个串的分割，那么整个字符串s的最少分割次数就是s[0: i]的最少分割次数 + 1。
      • 而s[0: i]的最少分割次数其实是需要把i从0到n - 2全部遍历一遍才知道哪一种分割的次数是最小的，那么s[0: i]的最少分割次数的求法，跟上述过程一样，可以递推。

注：s[0: i]是python中截取子串的表示方法，表示截取第0位到第i位的字符)

状态转移方程

令dp[i]表示s[0: i]的最少分割次数。

如果s[0: i]就是回文，那么dp[i]就是0。
如果s[0: i]不是回文，但是它的一个子串s[0: j]的最少分割次数已知(0 <= j < i)，并且s[j + 1: i]是回文，则 dp[i] = dp[j] + 1

最终结果就是求dp[n - 1]，从0开始递推就好了。

递推方程： dp[i] = min(dp[j]) + 1，其中0 <= j < i。

初始状态

  • 初始状态dp[0]就是s[0: 0]的最少分割次数，s[0: 0]就是首字符，单个字符是回文串，所以不用分割，dp[0] = 0。
  • 最坏的情况就是每个字符都分割，因为每个单字符都是回文，最大的分割次数就是n - 1，可以给dp数组初始化。

怎么快速判断s[i, j]是回文？

最好预处理整个s，把s的所有子串都判断一下是不是回文串，这样就可以做到O(1)的查表操作来快速判断了。

这里跟 131. 分割回文串 处理方式一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {

    fun minCut(s: String): Int {
        val n = s.length
        if (n <= 1) {
            return 0
        }
        val dp = IntArray(n)
        // s[0: i]的子串最大分割次数，就是每个字符都分割一下，分割i次（1 <= i < n）
        for (i in 0 until n) {
            dp[i] = i
        }
        for (i in 1 until n) {
            // 判断s[0:i]是不是回文
            if (isPalindrome(s, 0, i)) {
                // s[0:i]是回文，不用分割，最少分割次数是0
                dp[i] = 0
                continue
            }
            // s[0:i]不是回文，需要在[0,i)之间找到一个分割位置j，使得s[j+1:i]是回文，同时dp[j]最小
            // 需要从0开始遍历到i-1去寻找出最小的分割位置j
            // 这样也才能利用递推，利用之前存储过的状态，因为是从索引0开始递推的
            var minCut = Int.MAX_VALUE
            for (j in 0 until i) {
                if (isPalindrome(s, j + 1, i)) {
                    // s[j+1:i]是回文，dp[j]+1是dp[i]可能的一个取值，需要找一个最小的
                    minCut = minOf(minCut, dp[j] + 1)
                }
                // s[j+1:i]不是回文，当前的分割是无效的，就看下一个分割了，忽略当前的分割
            }
            // s[0:i]最大的分割次数，就是i次了，在前面已经初始化过了
            // 如果s[0:i]存在更少的分割，更新dp[i]的值
            if (minCut != Int.MAX_VALUE) {
                dp[i] = minCut
            }
        }
        return dp[n - 1]
    }

    private var dpStates: Array<Array<Boolean>>? = null

    /**
     * 判断字符串[s]索引从[start]到[end]的子串是否是回文
     */
    private fun isPalindrome(s: String, start: Int, end: Int): Boolean {
        val states = dpStates ?: getPalindromeStates(s)
        dpStates = states
        return states[start][end]
    }

    private fun getPalindromeStates(s: String): Array<Array<Boolean>> {
        val n = s.length
        val dp = Array(n) { Array(n) { false } }
        // 遍历所有长度的子串，length代表子串的长度，可以从1一直取值到n
        for (length in 1..n) {
            // 把所有是长度为length的子串都检查一遍，看是不是回文，start就要从0开始取值，一直取到n-length
            // start 是应该小于 n-length 还是小于等于?
            // 可以举例n为5，length为2，直观上看最后一个length为2的子串应该是s[3:4]，start为3，是n-length的结果
            for (start in 0..(n - length)) {
                // end和start之间保持相距length
                val end = start + length - 1
                if (start + 1 <= end - 1) {
                    dp[start][end] = dp[start + 1][end - 1] && s[start] == s[end]
                } else {
                    dp[start][end] = s[start] == s[end]
                }
            }
        }
        return dp
    }
}

时间复杂度：O(n^2)

n 是字符串 s 的长度。
预处理计算s所有子串是否是回文和动态规划计算s最小分割次数的时间复杂度均为 O(n^2)。

空间复杂度：O(n^2)

预处理计算s所有子串是否是回文需要O(n^2)的空间占用。
动态规划计算s最小分割次数需要O(n)的空间占用。