五、最长回文子串

待我称王封你为后i 2021-09-25 01:34 298阅读 0赞

# 题目描述： #

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

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

示例2：

输入: "cbbd"
    输出: "bb"

# 思路 #

1.  如果字符串长度小于 2，直接返回字符串
2.  定义两个变量，一个 start 存储当前找到的最大回文字符串的起始位置，另一个 maxLangth 记录字符串的长度
3.  判断左边和右边是否越界，同时最左边的字符等于最右边的字符，如果上述的条件都满足，则判断是否需要更新回文字符串最大长度及最大字符串的起始位置。然后将 left-- , right++，继续判断，直到不满足三个条件之一
4.  便利字符串，每个位置都直接步骤 3

# 解法 #

class Solution { 
        public String longestPalindrome(String s) { 
            int start = 0;
            int maxLength = 1;
            if (s.length() < 2) { 
                return s;
            }
            for (int i = 0; i < s.length(); i++) { 
                int left = i - 1;
                int right = i + 1;
                while (left >= 0
                        && right < s.length()
                        && s.charAt(left) == s.charAt(right)) { 
                    if (right - left + 1 > maxLength) { 
                        maxLength = right - left + 1;
                        start = left;
                    }
                    left--;
                    right++;
                }
            }
            for (int i = 0; i < s.length(); i++) { 
                int left = i;
                int right = i + 1;
                while (left >= 0
                        && right < s.length()
                        && s.charAt(left) == s.charAt(right)) { 
                    if (right - left + 1 > maxLength) { 
                        maxLength = right - left + 1;
                        start = left;
                    }
                    left--;
                    right++;
                }
            }
            return s.substring(start, start + maxLength);
        }
    }

--------------------

**博主的所有博客目录如下：[博客文章目录汇总][Link 1]  
Java面试部分的博客目录如下：[Java笔试面试目录][Java]**

> **转载请标明出处，原文地址：https://blog.csdn.net/weixin\_41835916 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。  
> ![这里写图片描述][70]**

[Link 1]: https://blog.csdn.net/weixin_41835916/article/details/81879208
[Java]: https://blog.csdn.net/weixin_41835916/article/details/81413498
[70]: /images/20210923/255296c31c564ffa8aad3ed40e9ef31b.png