用双端队列实现回文子串判定、动态规划实现高效查找

5. 题目链接-来源：力扣（LeetCode） （中等）

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

####思路：
这里借鉴了第3题中的『滑动窗口』思路，无非是把『无重复子串』变成了『回文子串』，自己再写一个判定回文的函数替换掉原先的条件即可即可。
当然本题也能用动态规划解。我们只要初始化长度为 1 和 长度为 2 子串 的 isPalindrome 状态并记录，即可避免重复计算，优化效率。即 我们以 s 中的每一个字符为起点，向两侧扩展，只要两头碰到的字符相同，即为回文串并更新最大长度，否则即停止扩展进入下一字符。
注意，我们既要以单个字符为起点，探讨奇数长度的字符串；也要以一对字符为起点。探讨偶数长度的字符串。因为我们每次扩展时长度增加 2，只能遍历奇数或者偶数中的某一种情况。
时间复杂度：O(n²) 遍历一次数组复杂度O(n)，判断是否回文的函数复杂度也为O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public String longestPalindrome(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int maxlen = 0;
        int rfi = 0;
        int rei;
        int fi;
        int ei;
        for (fi = 0; fi + maxlen < n; fi++) {
            char charF = arr[fi];
            for (ei = fi + maxlen; ei < n; ei++) {
                if (arr[ei] == charF && isPalindrome(arr, fi, ei)) {
                    int len = ei - fi + 1;
                    if (maxlen < len) {
                        maxlen = len;
                        rfi = fi;
                        rei = ei;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(arr, rfi, maxlen);
        return sb.toString();
    }
    
    private boolean isPalindrome(char[] chars, int fi, int ei) {
        while (fi < ei) {
            if (chars[fi] != chars[ei]) {
                return false;
            }
            fi++;
            ei--;
        }
        return true;
    }
}