5. longest palindromic substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

题目描述：

给出一个字符串，求最长回文子串

Solution:

两个指针high和low，指向两个相同的字符，分字符串长度为奇偶判断，找到相同的两个字符，high++，low–，最长回文就是high-low-1，每次循环更新找到最长回文

java:


public class  {
    public String longestPalindrome(String s) {
        int l=s.length();
        if(l<=1)
            return s;
        int maxLen=0,start=0;
        for(int i=1;i<l;i++){
           int low=i-1,high=i;
            while(low>=0&&high<l&&s.charAt(low)==s.charAt(high)){
                low--;
                high++;
            }
            if(high-low-1>maxLen){
                maxLen=high-low-1;
                start=low+1;
            }
            low=i-1;
            high=i+1;
            while(low>=0&&high<l&&s.charAt(low)==s.charAt(high)){
                low--;
                high++;
            }
            if(high-low-1>maxLen){
                maxLen=high-low-1;
                start=low+1;
            }
        }
        return s.substring(start,start+maxLen);
    }
}

5. longest palindromic substring

近期文章

近期评论

标签

热门

文章归档

分类目录

功能