❤️算法笔记❤️-(每日一刷-5、最长回文串)
文章目录
- 题目
- 思路
- 解答
题目
给你一个字符串
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);} }