5. 最长回文子串（高频题）

5. 最长回文子串

• 题目
• 解题思路
• 代码

题目

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

解题思路

把字符串的每一个字符当作中心，用左右指针向两侧扫描。记录每次的最长回文子序列，然后要注意奇数偶数的情况，详情见书374

代码

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


        String res = "";
        for (int i = 0; i < s.length(); i++) {
            //寻找长度为奇数的回文子串
            String s1 = palindrome(s, i, i);
            //寻找长度为偶数的回文子串
            String s2 = palindrome(s, i, i + 1);

            //res=longgest(res,s1,s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;

        }
        return res;
    }

    //返回以s[l]和s[r]为中心的最长回文子串
    public String palindrome(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            //从中间向两端扩散
            l--;
            r++;
        }

        //s.substring(l+1,r)：截取出来回文串，画个图一下就明白了
        return s.substring(l + 1, r);

    }
}