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

【LeetCode】#5最长回文子串(Longest Palindromic Substring)

程序员文章站 2024-02-24 17:51:52
...

【LeetCode】#5最长回文子串(Longest Palindromic Substring)

题目描述

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

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

示例

示例1:

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

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

示例2:

输入: “cbbd”
输出: “bb”

Input: “cbbd”
Output: “bb”

解法

class Solution{
	public String longestPalindrome(String s){
		if(s==null || s.length()<1)
			return "";
		int start = 0, end = 0;
		for(int i=0; i<s.length(); i++){
			int len1 = expandAroundCenter(s, i, i);
			int len2 = expandAroundCenter(s, i, i+1);
			int len = Math.max(len1, len2);
			if(len>end-start){
				start = i - (len-1)/2;
				end = i + len/2;
			}
		}
		return s.substring(start, end+1);
	}
	private int expandAroundCenter(String s, int left, int right){
		int L = left, R = right;
		while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)){
			L--;
			R++;
		}
		return R-L-1;
	}
}