Longest Palindromic Substring QuestionEditorial Solution

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

题目:给出一个字符串S,找到一个最长的连续回文串。

题解:
这里用到了一个叫Manacher’s Algorithm的算法。

算法首先将输入字符串S, 转换成一个特殊字符串T,转换的原则就是将S的开头结尾以及每两个相邻的字符之间加入一个特殊的字符

例如: S = “abaaba”, T = “#a#b#a#a#b#a#”
我们会发现无论原来的字符串经过这样处理后都会变成奇数的字符串,

现在假设S = “cabae”,则T = “#c#a#b#a#e#”,那么我们如何去求出aba呢?
以b为中心,假设b的坐标为i,你会发现:
T[i+1] = T[i-1]
T[i+2] = T[i-2]
T[i+3] = T[i-3]
T[i+4] ≠ T[i-4]
也就是以b为中心,左右3个字符都是分别相等的,而我们要求的“aba”也正好是3个字符,知道这些后,下面我们就可以开始鲁代码了

首先看get函数,我们这里并没有把字符串s重新用#拼接,而是根据传进来的索引返回,如果是偶数则返回#,否则返回s中对应的字符

然后看第10行的for循环,i就代表中心的位置,从1开始到s.length() * 2,如下图,i从a移动到c

sp160825_153830

count代表中心i的两边长度,i-count是左边界,i+count是右边界,通过get来判断两边字符是否相等,相等的话count加一,否则把多出来的1减回去

最后把count与max对比,如果count>max,则保存回文字符串到result

public class Solution {
    public String longestPalindrome(String s) {
        String result = "";
        if (s == null || s.length() == 0) {
            return result;
        }

        int max = 0;

        for (int i = 1; i < s.length() * 2; i++) {
            int count = 1;
            while (i - count >= 0 && i + count <= s.length() * 2 && get(s, i - count) == get(s, i + count)) {
                count++;
            }

            count--;
            if (count > max) {
                result = s.substring((i - count) / 2, (i + count) / 2);
                max = count;
            }
        }
        return result;
    }

    public char get(String s, int index) {
        if (index % 2 == 0) {
            return '#';
        } else {
            return s.charAt(index / 2);
        }
    }
}