首页 > itarticle > leetcode algorithms 5 最长回文子串 2. 题解

leetcode algorithms 5 最长回文子串 2. 题解

admin 11月 14, 2020 0

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1 2	输入: "cbbd" 输出: "bb"

2. 题解

2.1. 思路

Manacher算法

2.2. Java实现

class  {
    public String longestPalindrome(String s) {
        String t = "#";
        for (char c : s.toCharArray()) {
            t += c;
            t += '#';
        }
        int[] r = new int[t.length()];
        int pos = 0, maxLen = 0, maxRight = 0;
        String res = "";
        for (int i = 0; i < t.length(); i++) {
            r[i] = i < maxRight ? Math.min(maxRight - i, r[2 * pos - i]) : 1;
            while (i - r[i] >= 0 && i + r[i] < t.length() && t.charAt(i - r[i]) == t.charAt(i + r[i])) {
                ++r[i];
            }
            if (maxRight < i + r[i] - 1) {
                maxRight = i + r[i] - 1;
                pos = i;
            }
            if (r[i] > maxLen) {
                maxLen = r[i];
                res = t.substring(i - r[i] + 1, i + r[i]);
            }
        }
        return res.replaceAll("#", "");
    }
}