最长回文子串（遍历）

题意

给定字符串中最长回文子串有多长

思路分析

判断回文串

对于是不是回文串，可以通过从字符串的两边开始比较对称位置

for(int i = 0;i < s.length();i++){
    if(s[i] != s[s.length()-1-i])return false;
}
return true;

从中心向两侧判断

如果把方向改一改，从字符串的中心位置向两边搜索

int n = s.length();
for(int i = 0;i < n/2;i++){
    if(s[n/2-1-i] != s[n-n/2+i])return false;
}
return true;

相对于上面的从两边开始比较的判断方法，有两点优点

一是省去了重复判断的部分，上面会比较i和j也会比较j和i

一是如果想知道和原字符串同中心的最长回文串，从中心向两侧遍历能利用上一次的运算结果

奇偶长度处理

字符串长度是奇数还是偶数，中心有区别。

虽然上面知道了长度时，表达式相同，但实际上是因为利用了整除的性质。

对于奇数长度，中心是一个字符，所以向左向右的坐标分别为center-i,center+i

alt

对于偶数长度，中心是两个字符之间，所以向左向右的坐标分别为center-i,center+i+1

alt

记录最大值

对于每次枚举中合法的长度length更新最大值记录ans

ans = max(ans, length)

题解

所以整合上面的内容，先枚举奇偶，再枚举中心，再枚举长度。这样就能计算出最长回文串的长度

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        int ans = 0;
        int n = A.length();
        for(int i =0;i<n;i++){ // 奇数长度
            for(int l = 0;;l++){
                if(i-l < 0 || i+l >= n)break;
                if(A[i-l] != A[i+l])break;
                ans = max(ans,l*2+1);
            }
        }
        for(int i = 0;i<n;i++){ // 偶数长度
            for(int l = 0;;l++){
                if(i-l < 0 || i+l+1 >= n)break;
                if(A[i-l] != A[i+l+1])break;
                ans = max(ans,l*2+2);
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 先遍历中心，再遍历长度，所以总时间复杂度为 $O (n)$

空间复杂度: 只用了常数个额外变量，所以空间复杂度为 $O (1)$

题解 | #最长回文子串#