LeetCode 5. Longest Palindromic Substring(最长回文子串)
程序员文章站
2024-02-24 17:51:46
...
题目描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
解题思路
思路:采用的思路是遍历每个点,然后分别以每个点为中心向两边扩散的思想,只要两边的值相等就继续调整左右角标,继续向两边寻找,直到两者比较后不一样,在这个过程中不断更新最长子串和其长度。依然是放在循环中获取子串,循环的条件就是low和high角标没有超出字符串的范围。
单回文和双回文:单回文是以某个字符为对称中心去寻找,初始的low和high是重叠的,然后分别向两边寻找;双回文是以两个相邻的字符为起点向两边寻找,思路也是比较是否相等并不断扩散。双回文和单回文是需要分别的去求解的,最终取最长子串。
长度为0或者为1的字符串处理:这类的字符串只要直接返回就可以了,它就是最长子串。
代码实现
class Solution {
public String str="";
public int length=0;
public static void main(String[] args){
System.out.println(new Solution().longestPalindrome("cbbd"));
}
public String longestPalindrome(String s) {
if(s.length()<=1){
return s;
}
for(int i=0;i<s.length()-1;i++){
get(s,i,i);
get(s,i,i+1);
}
return str;
}
public void get(String s,int low,int high){
while(low>=0&&high<s.length()){
if(s.charAt(low)==s.charAt(high)){
if((high-low+1)>length){
length=high-low+1;
str=s.substring(low, high+1);
}
low--;
high++;
}else{
break;
}
}
}
}
推荐阅读