5 longest palindrome substring，longestpalindrome

5 longest palindrome substring，longestpalindrome

第一眼看这题，只觉得要从中间开始向两端延伸，通过扫一遍所有的字母来实现。。。

但是代码不是特别好写，因为有奇数和偶数的两种情况。。。

既然这样，那就设计一个helper 方法，然后引入两个index，可以是相同的，代表奇数长度substring，也可以是相邻的，代表偶数长度substring

public class Solution{

private int lo, maxLen;

public String longestPalindrome(String s) {
	int len = s.length();
	if (len < 2)
		return s;
	
    for (int i = 0; i < len-1; i++) {
     	extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
     	extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
	while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
		j--;
		k++;
	}
	if (maxLen < k - j - 1) {
		lo = j + 1;
		maxLen = k - j - 1;
	}

/*    int start=0;
    int len=0;
    
    public String longestPalindrome(String s) {
        if(s.length()==1) return s;
        for(int i=0; i<s.length(); i++){
            extend(s, i, i); // in case s has odd number of characters;
            extend(s, i, i+1); // in case s has odd number of characters;
        }
        return s.substring(start, start+len);
    }
    
    private void extend(String s, int left, int right){
        while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
       
        if(right-left-1>len){
            start=left++;
            len= right-left-1;
        }*/
        // here I only need to return the need the two index, or one index and the length;
    
        
    // 以下是1月初做的，超时了。。。可能是while循环 无限进行下去了。。。也有可能程序正确但复杂度高。。。参考了别人的解法后，我来重现一下。。。见上方
/*        String result= "";
        for(int i=0; i<s.length(); i++){
            int left=i-1;
            int right=i+1;
            while((left>=0)&&(right<s.length())){
                if(s.charAt(left)==s.charAt(right)){
                    left--;
                    right++;
                }
                else if(s.charAt(left)!=s.charAt(right)){
                    break;
                }
            }

            String tmp=s.substring(left+1, (right-1)+1); //wrong memory, correct: substring(begin, end), not substring(begin, length)
            //result=result.length()>tmp.length()?result:tmp; // this is right, just to adjuct to the output in the question.
            result=result.length()<tmp.length()?tmp:result;

            
            int leftEven=i;
            int rightEven=i+1;
            while((leftEven>=0)&&(rightEven<s.length())){
                if(s.charAt(leftEven)==s.charAt(rightEven)){
                    leftEven--;
                    rightEven++;
                }
                else if(s.charAt(leftEven)!=s.charAt(rightEven)){
                    break;
                }
            }

            String tmpEven=s.substring(leftEven+1, (rightEven-1)+1); //wrong memory, correct: substring(begin, end), not substring(begin, length)
            //result=result.length()>tmp.length()?result:tmp; // this is right, just to adjuct to the output in the question.
            result=result.length()<tmpEven.length()?tmpEven:result;

            
            // here I am re-using a lot of codes, so a helper() will be better
            
        }
        return result;*/
    }
}

// I did not consider "bb"

今天的代码，写得简单多了。。。

public class Solution{
    public String longestPalindrome(String s) {
        int low=0;
        int high=0;
        
        int len=1;// smallest
        for(int i=0; i<s.length()-1; i++){ // 只需到倒数第二位
            int len1=pali(s,i,i);
            if(len1>len){
                len=len1;
                low=i-(len1-1)/2;
                high=i+(len1-1)/2;
            }
            
            int len2=pali(s,i,i+1);
            if(len2>len){
                len=len2;
                low=i-(len2/2-1);
                high=i+1+(len2/2-1);
            }
        }
        return s.substring(low,high+1);  // error: s.subtring(low, high);
    }
    
    private int pali(String s, int l, int r){
        while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }
        return (r-1)-(l+1)+1;
    }
    
}