Ricky.L的随笔
0%

LeetCode.5.最长回文子串（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.5.最长回文子串（中等）

给你一个字符串 s，找到 s 中最长的回文子串。

题解

解法1：动态规划

最值问题考虑动态规划，先拆分大问题为子问题+有限步骤。

判断一个字符串是不是回文串，先看字符串两端字符是否相同，然后去除首尾两端字符后的剩余字符串如果是回文串，整个字符串就是回文串。
剩余字符串是不是回文串判断方法是一样的。
整个判断可以递归进行，符合最优子结构，无后效性。
重叠子问题也有，长度大的回文串是由长度小的回文串推导而来，而长度相同的字符串有很多，会有重复判断。

状态转移方程
设dp[i][j]为s[i, j]是否为回文串。
dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]

边界处理
字符串s长度只有1时，是对称的，是回文串，dp[i][j] = 1。
字符串s为2时，去除首尾字符后没有子串了，只需要判断首尾字符是否相同即可，dp[i][j] = s[i] == s[j]。

结果如何求解
要遍历所有长度的子字符串，寻找有没有回文串，并记录最大长度的回文串。
长度相同的子字符串有很多，都要列举出来。

复杂度
设字符串长度为n。
穷举所有长度子串需要O(n)时间。
穷举每个长度的可能的子串也需要O(n)时间。
总的时间复杂度$O(n^2)$。

用二维数组记录了所有子串的是否是回文串状态，空间复杂度$O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun longestPalindrome(s: String): String {
        val n = s.length
        val dp = Array(n) { i -> BooleanArray(n) { j -> i == j } }
        var maxLen = 1
        var maxLeft = 0
        for (len in 2..n) {
            // 穷举子串左端起点
            for (l in 0..(n - len)) {
                // 子串右端终点
                val r = l + len - 1
                dp[l][r] = if (s[l] == s[r]) {
                    if (len <= 3) true
                    else dp[l + 1][r - 1]
                } else false
                if (dp[l][r] && len > maxLen) {
                    maxLen = len
                    maxLeft = l
                }
            }
        }
        return s.substring(maxLeft, maxLeft + maxLen)
    }
}

解法2：中心扩散

解法1动态规划是从外向里判断的，也可以从里向外扩散判断。

穷举所有所有可能的中心点，向左右两端扩散，如果左右两端字符相同，说明能构成回文串，再继续扩散查看。

但是回文的中心点有两种可能。
回文串字符数是奇数，中心只有一个字符。
回文串字符数是偶数，中心有两个字符。

不知道哪种中心扩散生成的回文串长度最大，那就两个都试一下，取最大值。

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
class Solution {
    fun longestPalindrome(s: String): String {
        val n = s.length

        fun centerSpread(l: Int, r: Int): String {
            var left = l
            var right = r
            while (left >= 0 && right < n) {
                if (s[left] != s[right]) break
                left--
                right++
            }
            // 在这里扩散完发现的回文串索引范围是[left + 1, right - 1]
            return s.substring(left + 1, right)
        }

        var longest = ""
        for (i in 0 until n) {
            val odd = centerSpread(i, i)
            val even = centerSpread(i, i + 1)
            val longer = if (odd.length > even.length) odd else even
            if (longer.length > longest.length) longest = longer
        }
        return longest
    }
}

复杂度
穷举中心点，需要遍历所有元素，消耗时间$O(n)$。
从中心点向两边扩散，最多扩展到整个字符串，所以最大消耗时间$O(n)$。
总体时间复杂度$O(n^2)$。

没有占用额外存储空间，空间复杂度$O(1)$。