欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    		}    		
    	}    	
    }   
}