博客

如何高效的在一个字符串中找到最长的回文子串呢？下面我们根据代码来分析

首先，回文串有两种，一种是字符串的长度是偶数，另一种就是奇数。我们从字符串第二个字符开始，我们把当前起始字符叫做i。

先检验奇数长度的字符串，对比该字符的前一个和后一个(i – 1 和 i + 1)，一共三个字符(奇数个)，如果前后字符相同则说明是回文串，就把当前字符与保存的回文palindromic进行比较，如果长度比较长，就把palindromic替换。然后接着首指针继续往前移动一格，后指针后移一格。继续判断，直到不是回文，或者首和末两者其中一个超过字符串合法长度。

奇数长度判断完了，接着到偶数。偶数起始位置就是当前字符i和前一个字符(i – 1)。先判断这两个字符是否相等，如果相等，接着前后各移动一格，条件和奇数一样。

当以上两个都判断完了之后，i++。

public String longestPalindrome(String s) {
    // 如果回字符串长度小于2直接返回
    if(s.length() < 2) {
        return s;
    }
    // 记录最长的回文串
    String palindromic = "";
    int j, k;
    for(int i = 1; i < s.length(); i++) {
        if(s.length() - i <= palindromic.length() / 2) {
            break;
        }
        int sum = 1;
        // 奇数长度判断
        for(j = i - 1, k = i + 1; j >= 0 && k < s.length(); j--, k++) {
            if(s.charAt(j) != s.charAt(k)) {
                break;
            }
            sum = sum + 2;
        }
        if(sum > palindromic.length()) {
            palindromic = s.substring(j + 1, k);
        }
        sum = 0;
        // 偶数长度判断
        for(j = i - 1, k = i; j >= 0 && k < s.length(); j--, k++) {
            if(s.charAt(j) != s.charAt(k)) {
                break;
            }
            sum = sum + 2;
        }
        if(sum > palindromic.length()) {
            palindromic = s.substring(j + 1, k);
        }
    }
    return palindromic;
}