题目描述
LC 题 - 5
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
题解
思路1:暴力枚举
枚举所有子串，判断是否是回文串
// OC
+ (NSString *)longestPalindrome1:(NSString *)str {
if (str.length < 2) {
return str;
}
NSString *res = @"";
for (int i=0; i<str.length; i++) {
for (int j=i; j<str.length; j++) {
NSString *tempStr = [str substringWithRange:NSMakeRange(i, j-i+1)];
// 当前字符串长度小于已记录的最大回文串长度 continue
if (tempStr.length < res.length) {
continue;
}
if ([self isPalindrome:tempStr] && tempStr.length > res.length) {
res = tempStr;
}
}
}
return res;
}
+ (BOOL)isPalindrome:(NSString *)str {
BOOL res = YES;
int left = 0;
int right = (int)str.length - 1;
while (left>=0 && right<str.length) {
if ([str characterAtIndex:left] != [str characterAtIndex:right]) {
res = NO;
break;
}
left ++;
right --;
}
return res;
}
// Swift
static public func longestPalindrome1(_ s:String) -> String {
if s.count < 2 {return s}
var res = String()
for i in 0..<s.count {
for j in i..<s.count {
let startIndex = s.index(s.startIndex, offsetBy: i)
let endIndex = s.index(s.startIndex, offsetBy: j+1)
let tempStr = s.substring(with: startIndex..<endIndex)
if tempStr.count < res.count {
continue
}
if isPalindrome(tempStr) && tempStr.count > res.count {
res = tempStr
}
}
}
return res
}
// 判断是否是回文串
static func isPalindrome(_ s:String) -> Bool {
var res : Bool = true
let chars:[Character] = Array(s)
if chars.count < 1 {return res}
var left = 0
var right = chars.count - 1
while left < right {
if chars[left] != chars[right] {
res = false
break
}
left += 1
right -= 1
}
return res
}
思路2:动态规划
对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串“ababa”，如果我们已经知道“bab” 是回文串，那么“ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。
根据这样的思路，我们就可以用动态规划的方法解决本题。
我们用P(i,j) 表示字符串s的第i到j 个字母组成的串（下文表示成s[i:j]）是否为回文串： P(i,j) 为true，则表示如果子串 si...sj是回文串，P(i,j)为false,则有两种情况：1是s[i,j]本身不是回文串 2是j<i 不合法。
那么我们就可以写出动态规划的状态转移方程：
P(i,j) = P(i+1,j-1) && (si==sj)
也就是说，只有s[i+1:j−1] 是回文串，并且s 的第i 和j 个字母相同时，s[i:j] 才会是回文串。
我们来看下动态规划的边界条件
上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为1 或2。对于长度为1 的子串，它显然是个回文串；对于长度为2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：
P(i,i) = true, P(i,i+1) = (s(i) == s(i+1))
根据这个思路，我们就可以完成动态规划了，最终的答案即为所有P(i,j)=true 中j−i+1（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。
// OC
+ (NSString *)longestPalindrome2:(NSString *)str {
if (str.length < 2) {
return str;
}
int n = (int)str.length;
int maxlen = 1;
int start = 0;
BOOL dp[n][2];
// 初始化：所有长度为 1 的子串都是回文串
for (int i=0; i<n; i++) {
dp[i][i] = YES;
}
// 遍历子串长度
for (int k=2; k<=n; k++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i=0; i<n; i++) {
// j-i+1 = k
int j = k+i-1;
if (j>=n) {
break;
}
// j-1 > i+1
if (j-i>2) {
dp[i][j] = dp[i+1][j-1] && ([str characterAtIndex:i] == [str characterAtIndex:j]);
}else{
dp[i][j] = [str characterAtIndex:i] == [str characterAtIndex:j];
}
if (dp[i][j] && j-i+1 > maxlen) {
maxlen = j-i+1;
start = i;
}
}
}
return [str substringWithRange:NSMakeRange(start, maxlen)];
}
// Swift
static public func longestPalindrome2(_ s:String) -> String {
if s.count < 2 {return s}
let sArr = s.map({ String.init($0)})
let n = sArr.count
var maxLen = 1
var begin = 0
var dp:[[Bool]] = Array(repeating: Array(repeating: true, count: n), count: n)
// 初始化：所有长度为 1 的子串都是回文串
for i in 0..<n {
dp[i][i] = true
}
// 先枚举子串长度
for k in 2..<(n+1) {
// 枚举左边界，左边界的上限设置可以宽松一些
for i in 0..<n {
// 由 k 和 i 可以确定右边界，即 j - i + 1 = k 得
let j = k+i-1
if j >= n {
break
}
// j-1要大于i+1 j-1>i+1
if j-i>2 {
dp[i][j] = dp[i+1][j-1] && (sArr[i] == sArr[j])
}else{
dp[i][j] = sArr[i] == sArr[j]
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if dp[i][j] && (j-i+1 > maxLen) {
maxLen = j-i+1
begin = i
}
}
}
let subArray = sArr[begin..<(begin+maxLen)]
return subArray.joined()
}
思路3: 中心扩展算法
枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。对所有的长度求出最大值，即可得到最终的答案。
回文中心 对于i位置可能有两个 i 或者 （i，i+1）
举个例子“abba” 它的回文中心为b,b。“aba” 它的回文中心是b
// OC
+ (NSString *)longestPalindrome3:(NSString *)str {
if (str.length < 2) {
return str;
}
int maxlen = 1;
int start = 0;
for (int i=0; i<str.length; i++) {
int len1 = [self expandAroundCenter:str left:i right:i];
int len2 = [self expandAroundCenter:str left:i right:i+1];
int len = MAX(len1, len2);
if (len > maxlen) {
maxlen = len;
start = i-(len-1)/2;
}
}
return [str substringWithRange:NSMakeRange(start, maxlen)];
}
+ (int)expandAroundCenter:(NSString *)str left:(int)left right:(int)right {
while (left>=0 && right<str.length && ([str characterAtIndex:left] == [str characterAtIndex:right])) {
left --;
right ++;
}
// 此处是right-left - 1 而不是right-left+1，是由于出循环时，right+1 left-1了，也就说长度多加了2
return right-left - 1;
}
// Swift
static public func longestPalindrome3(_ s:String) -> String {
if s.count < 2 {return s}
var sArray = s.map({ String.init($0)})
var start = 0
var end = 0
var maxLen = 0
for i in 0..<sArray.count {
let len1 = expandAroundCenter(sArray, i, i)
let len2 = expandAroundCenter(sArray, i, i+1)
maxLen = max(len1, len2)
if maxLen > end - start {
start = i - (maxLen-1)/2
end = i+(maxLen)/2
}
}
let subArray = sArray[start...end]
let sub = subArray.joined()
return sub
}
static func expandAroundCenter(_ arr:[String], _ l:Int, _ r:Int) -> Int {
var left = l
var right = r
while (left >= 0 && right < arr.count && (arr[left] == arr[right])) {
left -= 1
right += 1
}
// 此处是right-left - 1 而不是right-left+1，是由于出循环时，right+1 left-1了，也就说长度多加了2
return right-left-1
}
思路4: Manacher 算法 (马拉车算法)
回文串有两种形式，一种是奇数的比如"aba"，一种是偶数的比如"abba"。这里使用Manacher算法的时候，会在每个字符之间都会插入一个特殊字符，并且两边也会插入，这样无论原来字符串长度是奇数还是偶数，添加之后长度都会变成奇数
"aba"-->"#a#b#a#"（长度是7）
"abba"-->"#a#b#b#a#"（长度是9）
通过添加特殊字符，原来字符串长度无论是奇数还是偶数最终都会变为奇数，因为特殊字符的引用，改变之后的字符串的所有回文子串长度一定都是奇数。并且回文子串的第一个和最后一个字符一定是你添加的那个特殊字符。
添加特殊字符后的字符串的回文子串的长度和原始字符串的回文子串的长度关系：
（预处理字符串的回文子串的长度-1）/2 = 原始字符串的回文子串的长度 = 以i为中心向两边能扩散的步数
这里再来引用一个变量叫回文半径，因为添加特殊字符之后所有回文子串的长度都是奇数，我们定义回文子串最中间的那个字符到回文子串最左边的长度叫回文半径
Manacher 算法的核心是利用动态规划和中心扩散算法，计算i位置的最大回文串长度时，尽可能参考i关于当前center对称点j(2center-i)的最大回文串长度
假如以当前字符s[maxCenter]为回文中心的最大回文长度是从left到maxRight，如下图所示
如果我们想求以字符s[i]为回文中心的最大回文长度，我们只需要找到i关于maxCenter的对称点j，看下j的回文长度，因为j已经计算过了。
1、如果i在maxRight的左边，并且j的最大回文长度左边没有到达left，根据对称性，i的最大回文长度就等于j的最大回文长度
2、如果i在maxRight的左边，并且j的最大回文长度左边到达或者超过left，根据对称性，i的最小回文长度等于j-left也等于maxRight-i，至于最大能有多大，还需要在继续判断
3、如果i在maxRight的右边，我们就没法利用之前计算的结果了，这个时候就需要一个个判断了
如果p[i] + I大于maxRight，我们就更新maxCenter 和 maxRight
如果还看不明白，我们来随便找个字符串"babcbabcbac"画个图来看下
// OC
+ (NSString *)longestPalindrome4:(NSString *)str {
if (str.length < 2) {
return str;
}
//源字符串的长度
int orgCharLen = (int)str.length;
// 添加特殊字符 字符长度
int newCharLen = 2*orgCharLen + 1;
NSMutableArray *newCharArray = [[NSMutableArray alloc] init];
// 添加特殊字符 #
for (int i=0; i<orgCharLen; i++) {
[newCharArray addObject:@"#"];
[newCharArray addObject:[str substringWithRange:NSMakeRange(i, 1)]];
}
[newCharArray addObject:@"#"];
//maxRight(某个回文串延伸到的最右边下标)
//maxCenter(maxRight所属回文串中心下标),
//resCenter（记录遍历过的最大回文串中心下标）
//resLen（记录遍历过的最大回文半径）
int maxRight = 0, maxCenter = 0, resLen = 0, resCenter = 0;
// p数组 ，p[i]表示以newCharArray[i]为中心的回文串半径
int p[newCharLen];
for (int i=0; i<newCharLen; i++) {
if (i<maxRight) {
//情况一，i没有超出范围[left,maxRight]
//2 * maxCenter - i其实就是j的位置，实际上是判断p[j]<maxRight - i
if (p[2*maxCenter-i] < maxRight-i) {
p[i] = p[2*maxCenter - i];
}else{
//情况二，j的回文半径已经超出了范围[left,maxRight]，我们可以确定p[i]的最小值
//是maxRight - i，至于到底有多大，后面还需要在计算
p[i] = maxRight - i;
while (i-p[i] >= 0 && i+p[i] < newCharLen && ([newCharArray[i-p[i]] isEqualToString:newCharArray[i+p[i]]])) {
p[i] ++ ;
}
}
}else{
//情况三，i超出了范围[left,maxRight]，就没法利用之前的已知数据，而是要一个个判断了
p[i] = 1;
while (i-p[i] >= 0 && i+p[i] < newCharLen && ([newCharArray[i-p[i]] isEqualToString:newCharArray[i+p[i]]])) {
p[i] ++ ;
}
}
if (p[i] + i > maxRight) {
maxRight = p[i] + i;
maxCenter = i;
}
if (p[i] > resLen) {
resLen = p[i];
resCenter = i;
}
}
// resLen*2-1 是加特殊字符的回文串长度
// 原始回文串的长度 = （加特殊字符的回文串长度 - 1）/2
int len = (resLen * 2 - 1 -1)/2;
int start = (resCenter - resLen + 1)/2;
return [str substringWithRange:NSMakeRange(start, len)];
}
// Swift
static public func longestPalindrome4(_ s:String) -> String {
if s.count < 2 {return s}
//源字符串的长度
let orgCharLen = s.count
//源字符串的字符数组
let orgCharArray = s.map({ String.init($0)})
let newCharLen = 2*orgCharLen + 1
var newCharArray = [String]()
// 添加特殊字符
for i in 0..<orgCharLen {
newCharArray.append("#")
newCharArray.append(orgCharArray[i])
}
newCharArray.append("#")
// p数组 ，p[i]表示以newCharArray[i]为中心的回文串半径
var p:[Int] = Array(repeating: 0, count: newCharLen)
//maxRight(某个回文串延伸到的最右边下标)
//maxCenter(maxRight所属回文串中心下标),
//resCenter（记录遍历过的最大回文串中心下标）
//resLen（记录遍历过的最大回文半径）
var maxRight = 0
var maxCenter = 0
var resCenter = 0
var resLen = 0
// 遍历新数组 newCharArray
for i in 0..<newCharLen {
if i<maxRight {
//情况一，i没有超出范围[left,maxRight]
//2 * maxCenter - i其实就是j的位置，实际上是判断p[j]<maxRight - i
if p[2*maxCenter-i] < maxRight - i {
p[i] = p[2*maxCenter-i]
}else{
//情况二，j的回文半径已经超出了范围[left,maxRight]，我们可以确定p[i]的最小值
//是maxRight - i，至于到底有多大，后面还需要在计算
p[i] = maxRight - i
while(i-p[i] >= 0 && i+p[i] < newCharLen && newCharArray[i-p[i]] == newCharArray[i+p[i]]) {
p[i] += 1
}
}
}else{
//情况三，i超出了范围[left,maxRight]，就没法利用之前的已知数据，而是要一个个判断了
p[i] = 1
while(i-p[i] >= 0 && i+p[i] < newCharLen && newCharArray[i-p[i]] == newCharArray[i+p[i]]){
p[i] += 1
}
}
//匹配完之后，如果右边界i + p[i]超过maxRight，那么就更新maxRight和maxCenter
if p[i] + i > maxRight {
maxRight = p[i] + i
maxCenter = i
}
//记录最长回文串的半径和中心位置
if p[i] > resLen {
resLen = p[i]
resCenter = i
}
}
// 计算最长回文串的长度和开始的位置
let start = (resCenter - resLen + 1)/2
// resLen*2-1 是加特殊字符的回文串长度
// 原始回文串的长度 = （加特殊字符的回文串长度 - 1）/2
resLen = (resLen*2-1-1)/2
let subArray = orgCharArray[start..<(start+resLen)]
return subArray.joined()
}
参考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvn3ke/?discussion=erC4Kz
