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

ゝ一纸荒年。 2023-10-05 20:49 42阅读 0赞

#### 5. 最长回文子串 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给你一个字符串 s，找到 s 中最长的回文子串。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

把字符串的每一个字符当作中心，用左右指针向两侧扫描。记录每次的最长回文子序列，然后要注意奇数偶数的情况，详情见书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);
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210301135940312.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70