Longest Palindromic Substring,Leetcode 解题笔记

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.

首先明确什么是Palindromic String,其实就是以string中心左右对称的string,比如”abccba”就是一个Palindromic String。

思路很直接,遍历String s,在每个遍历到的字符处向左右延展,判断是否为Palindromic String,是则截取出来与当前最长的结果longest比长度,然后更新longest。此算法时间复杂度是O(n^2)。

注意两点:
1. 开始时要处理特殊情况。
2. 对于Palindromic String,有两种情况,一种是单字符中心,如”abcba”,另一种则是双字符中心,如”abccba”,这两种情况需要分别处理。

具体代码如下:

public class Solution {
    public String longestPalindrome(String s) {
        
        //special cases
        if(s.length() == 0) return null;
        if(s.length() == 1) return s;
        
        //initialize longest palindrome substring
        String longest = s.substring(0,1);
        
        //in the case the center of the palindrome substring is single character
        for(int i = 0; i < s.length(); i++){
            String p = getPalindrome(s, i, i);
            if(p.length() > longest.length()){
                longest = p;
            }
        }
        
        //in the case the center of the palindrome substring are two characters
        for(int i = 0; i < s.length(); i++){
            String p = getPalindrome(s, i, i+1);
            if(p.length() > longest.length()){
                longest = p;
            }
        }
        
        return longest;
    }
    
    //get current palindrome substring
    public static String getPalindrome(String s, int start, int end){
        while(start >= 0 && end < s.length()){
            if(s.charAt(start) == s.charAt(end)){
                start--;
                end++;
            }
            else{
                break;
            }
        }
        return s.substring(start+1, end);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s