公司建设网站公司网站 设计 语言

题目

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

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

Related Topics

双指针

字符串

动态规划

👍 7405

👎 0

思路

双指针的套路之一：

1、先写一个方法用于判断回文串。用到双指针技巧，指针从中间朝两边扩散。
2、判断回文串的难点在于：回文串的长度可能是奇数，也可能是偶数。
3、思路：
for I I<s.length()
奇数项回文串
偶数项回文串
更新答案

解答

根据上面的框架套答案：

class Solution {public String longestPalindrome(String s) {String res="";for(int i=0;i<s.length();i++){String s1=palindrome(s,i,i);String s2=palindrome(s,i,i+1);res=res.length()>s1.length()?res:s1;res=res.length()>s2.length()?res:s2;}return res;}String palindrome(String s,int left,int right){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}return s.substring(left+1,right);}
}