Leetcode5 Longest Palindromic Substrings

题目描述

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

思路

如果len为n的string是回文字符那么长度为n-2的string也是回文字符。

abcbc -> bcb->c

abba -> bb

代码

class Solution {
    public String longestPalindrome(String s) {
        int star=0;
        int len =0;
        for(int i=0;i<s.length();++i){
            int cur = Math.max(getLen(s,i,i),getLen(s,i,i+1));
            if(cur> len){
                len=cur;
                star =i - (cur-1)/2;
            }
        }
        return s.substring(star,star+len);
    }
	private int getLen(String s, int l, int r){
    	while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
       		--l;
        	++r;
    	}
    	return r-l-1;
	}
}