动态规划、马拉车算法
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入： s = “babad”
输出： “bab”
解释： “aba” 同样是符合题意的答案。
示例 2：
输入： s = “cbbd”
输出： “bb”
示例 3：
输入： s = “a”
输出： “a”
示例 4：
输入： s = “ac”
输出： “a”
提示：
1 <= s.length <= 1000s 仅由数字和英文字母（大写和/或小写）组成
思路
这是一个经典的算法问题，解决该问题的方法有很多。典型的解法有双指针动态规划，中心求臂展解法，以及臂展解法的进阶解法马拉车算法。
三种解法的复杂度如下表。（设 n = s.length）
| 解决方法 | 时间复杂度 | 空间复杂度 |
|---|
| 普通动态规划 | O(n^2) | O(n^2) | | 臂展计算法 | O(n^2) | O(1) | | 拉马车算法 | O(n) | O(n) |
下面分别介绍下三种算法的解题思路。
普通动态规划解法
由于本问题要求的回文子串是一个子字符串，我们很自然的就会用s[i...j]定义该子串，其中j >= i。
那么，进一步思考的问题就是，如何判断s[i...j]是一个子串？
可以分三步来分析。
- 当子串长度为
1，即j - i == 0时，因为只有一个字符，该子串必然是回文子串。 - 当子串长度为
2，即j - i == 1时，显然只要s[i] == s[j]，该子串则为回文子串，否则就不是回文子串。 - 当子串长度大于
2，即j - i > 1时，要考察子串是否为回文子串，则需要进行如下考察。
针对情况3的考察。
- 如果
s[i] != s[j]，则该子串必然不是回文子串。 - 如果
s[i] == s[j]，则该子串是否是回文子串，取决于s[i+1...j-1]是否是回文子串。
经过以上的分析，我们成功的把该问题转换成了一个动态规划问题。
我们还可以对长度为1和2的边界条件做进一步优化，可以假定当字符串为空时，我们认为空字符串是特殊的回文子串。这么一来，情况2就可以被合并到情况3里。
将以上思路用代码进行表达。可以通过这样一个编码思路：
- 通过循环来遍历回文子串。
- 为了保证能通过动态规划缓存上一次的计算结果，我们先从长度为
2的回文子串开始进行查找（长度为1没必要查找），一直查到长度为n为止。 - 当我们查找长度为
l的子串时，由于循环迭代的关系，我们已经找过长度小于l的子串计算结果了，这样就可以通过读取上一次的计算结果进行本次计算。
代码如下。
class Solution {
func longestPalindrome(_ s: String) -> String {
let cs = s.cString(using: .ascii)!
let n = strlen(cs)
var c: [[Bool]] = Array(repeating: Array(repeating: false, count: n),
count: n)
guard n > 1 else { return s }
var maxlen = 0
var rng: (Int, Int) = (0, 0)
for l in 2...n {
for i in 0..<n-l+1 {
if cs[i] == cs[i+l-1] && (l <= 3 || c[i+1][i+l-2]) {
c[i][i+l-1] = true
if l > maxlen {
rng = (i, i+l-1)
maxlen = l
}
}
}
}
return String(cString: cs[rng.0...rng.1].map{$0} + [0])
}
}
由于该算法明显用了两层循环进行计算，而且还开辟了一个二维缓存数组。显然时间复杂度是O(n^2)，空间复杂度也是O(n^2)。
臂展计算法
因为回文串有一个特性，从串的中间往左右观察的话，可以发现左右两边是相等的，从这个思路出发就可以考虑到，任何回文串都存在一个中间界，当从中间界往左右扩散，必然可以得出左右两边的字符是相等的。
假定有一个回文串s[i..k..j]，且其长度为奇数，其中i<=k<=j，且k=(i+j)/2，那么k就是该回文串的中位数，当回文串足够长时，我们有s[k+1]=s[k-1]，s[k+2]=s[k-2]，s[k+3]=sk[k-3]……直到碰到i和j为止。
以上分析仅限于回文串长度为奇数时，那么当长度为偶数时呢，我们可以这样定义，对于一个回文串s[i..k..j]，且其长度为偶数，其中i<=k<=j，且k=(i+j-1)/2，那么k就是该回文串的中位数，当回文串足够长时，我们有s[k]=s[k+1]，s[k-1]=s[k+2]，s[k-2]=s[k+3]……直到碰到i和j为止。
通过对中位数k的分析，可以把循环的思路从“找i”引到“找k”，即我们扫描数组中的所有元素，并且我们寻找它是回文串的中位数时最长的回文串有多长，该长度我们称之为它的“臂展“。
由于前面分析的中位数k存在两种情况，即臂展为偶数和臂展为奇数的情况，所以我们需要设计一个函数来计算偶数和奇数情况下的臂展。
func searchSpan(_ k: Int, _ x: Bool) -> Int {
var i = 1
let t = x ? 0 : 1
while k - i + t >= 0 && k + i < n && cs[k-i+t] == cs[k+i] {
i += 1
}
return x ? i * 2 - 1 : (i - 1) * 2
}
在该函数searchSpan中，其参数k为中位数，参数x为布尔类型，知名所求回文串长度为奇数还是偶数。cs代表着字符串。
当循环i从1开始计数时，对于奇数臂展，求的是cs[i-1]和cs[i+1]的比较，而对于偶数臂展，求的是cs[i]和cs[i+1]的比较。
对于奇数和偶数，通过一个变量t来进行边界增量计算。
最后输出臂展的长度，同样是分奇数和偶数来计算。
有了求臂展函数，接下来的操作就相对简单了，我们只要遍历整个字符串，求得臂展，然后保存最大臂展和臂展的范围，当循环结束时，最大的臂展范围已经求得。
完整代码如下。
class Solution {
func longestPalindrome(_ s: String) -> String {
let cs = s.cString(using: .ascii)!
let n = strlen(cs)
func searchSpan(_ k: Int, _ x: Bool) -> Int {
var i = 1
let t = x ? 0 : 1
while k - i + t >= 0 && k + i < n && cs[k-i+t] == cs[k+i] {
i += 1
}
return x ? i * 2 - 1 : (i - 1) * 2
}
var maxLen = 0
var rng = (0, 0)
for k in 0..<n {
let l1 = searchSpan(k, true)
let l2 = searchSpan(k, false)
let l = max(l1, l2)
if l > maxLen {
rng = l1 > l2 ? (k-l1/2, k+l1/2) : (k-l2/2+1, k+l2/2)
maxLen = l
}
}
return String(cString: cs[rng.0...rng.1].map{$0}+[0])
}
}
该算法总共有两层循环，不难分析出其时间复杂度为O(n^2)，由于该算法额外开辟的空间是常量级别，故其空间复杂度为O(1)。
马拉车算法
马拉车算法的英文名叫Manacher‘s Algorithm，是一个卡内基梅隆大学的计算机教授Glenn Keith Manacher发明的算法，该算法可以实现在O(n)时间复杂度内解决最大回文子串的查找问题。
马拉车算法事实上是臂展算法的改进版。它的起点思路和臂展算法是一致的，即计算每个遍历节点的臂展，但是它会保存臂展的结果以便于下次可以”跳过”不必要的计算。
我们假设对于字符串s，遍历i求其臂展，并且位置i的臂展长度是奇数，那么s[i]必然位于该回文子串的正中央位置，将臂展长度分为左右两侧的等臂，取右臂的长度为l，那么，当我们将i向后遍历到j时，如果j还在臂展范围内，我们会发现当l足够长时，因为i左右两侧的数值是镜像关系，对于s[j]，必然存在臂展左边的镜像s[i-(j-i)]，而因为左侧的对应位置我们已经计算过其臂展，那么对于位置j，我们就可以“跳过”镜像已经计算过的部分。
举例字符串：“pkabacabacu”
对于该字符串，我们可以算出位置5，即字符c的位置，其臂展为7，即回文串“abacaba”，我们假设已知位置5，即c字符的臂展为7，那么再往后查找时，当我们查找到右侧的位置a时，由于左边“镜像”的存在，我们提前知道了左侧a的臂长为1，那么在计算右侧的a的时候，我们自然知道它的臂长“至少为1”，这样我们只要跳过1的位置去比较即可。同理，对于b，由于左侧镜像臂展是3，即右侧单臂长度为1，我们在求臂展时就可以跳过这个臂展去计算新的位置，而不用从头进行计算。但是要注意，可以跳过的位置必须是在“臂展笼罩范围内”。
有了以上的“跳过”思路，我们从新审视求臂展算法，就可以知道，当我们对字符串进行遍历去求臂展时，我们每次都可以得到臂展最长的“染指”部分，比如假设i的位置为5，而它的臂展为7，那么它的右侧单臂长度就是3，它的“手臂”可以延伸到位置8，那么这就意味着，位置6、7，8都被“笼罩在”5的臂展范围，这样我们在计算它们时始终有对应的镜像进行“跳过”参照。根据贪心思路，我们在遍历数组时始终都会保留那个最大的笼罩范围进行计算。
问题分析到这里，我们还遇到一个问题，就是我们之前讨论的是臂展长度为奇数的情况，那么对于臂展为偶数的情况怎么计算？
这里提供了一个解决问题的思路：“填充法”。举字符串“baab”为例，它是一个回文串，且臂展为偶数。接下去看用填充法怎么做到用奇数的思路去找到它，首先对字符串的每个间隔添加字符#，字符串就变成“b#a#a#b”，那么，新的字符串对于位置3的字符#，我们找到了以它为中心的奇数回文串，而只要我们把得到的回文串清除占位符#，即可得到原回文串“baab”。
基于该算法思路编写的完整swift代码如下：
class Solution {
func longestPalindrome(_ s: String) -> String {
let cr = s.cString(using: .ascii)!
var n = strlen(cr)
var cs: [CChar] = Array(repeating: 0, count: n*2)
var i = 0
while cr[i] != 0 {
cs[i*2] = cr[i]
i += 1
}
n = n * 2 - 1
var c: [Int] = Array(repeating: 0, count: n)
func searchPalindrome(_ p: Int, _ o: Int) -> Int {
var i = o
while p - i >= 0 && p + i < n && cs[p - i] == cs[p + i] {
i += 1
}
return i - 1
}
var j = 0
var l = 0
var maxlen = 0
var rng: (Int, Int) = (0, 0)
for i in 0..<n {
var o = 1
if i < l {
o = min(c[j-(i-j)], l-i)
}
let k = searchPalindrome(i, o)
var len = k / 2 * 2 + 1
if cs[i] == 0 {
len = (k+1) / 2 * 2
}
if len > maxlen {
maxlen = len
rng = (i-k, i+k)
}
if i + k > l {
l = i + k
j = i
}
c[i] = k
}
var ans: [CChar] = []
for i in rng.0...rng.1 {
if cs[i] != 0 {
ans.append(cs[i])
}
}
ans.append(0)
return String(cString: ans)
}
}
该算法由于每次都利用了原先的计算结果进行跳步，其时间复杂度为O(n)，而因为需要和n同等规模的存储空间，空间复杂度也为O(n)。
如果对马拉车算法感兴趣想进一步延伸阅读，可以看看一些介绍比较全面的国外文章，比如：https://vnspoj.github.io/wiki/string/manacher 。
小结
该题解法可难可易，一般如果是作为竞赛或者面试，方法一和二足矣，马拉车算法更适合平时学习和尝试，其实现过程并不简单，涉及到不少边界计算，也考验编码严谨程度。
所有代码均可以在 github 下载 : https://github.com/FengHaiTongLuo/LeetCode4Swift/blob/main/5.%20Longest%20Palindromic%20Substring.swift
通过公众号“风海铜锣技术君”点击菜单可以加进“程序员不卷群”一起交流算法和面经。
|