AC Java solution


  • 0
    G

    I saw this algorithm in leetcode, but it was accpted 3 years ago and could not pass some of test cases, so I made some modifications. Acctually my algorithm was "TLE".
    The main idea of this algorithm is checking every letter's both left and right sides if they math each other, then regarding it as a palindrome and there two kinds of palindrome in this algorithm "aba" and "cbbc". Here is the code.

    public  static String longestPalindrome(String s) {
    	if(s.length()<=1){
    		return s; 
    	}
    	int l=0,r=0;
    	for(int start=0;start<s.length();start++){
    		int []tmp=judgePalindrome(s,start,start);// "aba" type palindrome
    		int []temp=judgePalindrome(s,start,start+1); // "cbbc" type palindrome
                        // choose the max-length palindrome
    		if((tmp[1]-tmp[0])>(temp[1]-temp[0]) ){
    			if((tmp[1]-tmp[0])>r-l){
    				l=tmp[0];
    				r=tmp[1];
    			}
    		}else{
    			if((temp[1]-temp[0])>r-l){
    				l=temp[0];
    				r=temp[1];
    			}
    		}
    	}
    	return s.substring(l,r+1);
    }
    public static int[] judgePalindrome(String s, int left,int right){
    	int l=0,r=0;
    	while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
    		left--;
    		right++;
    	}
    	if(right-left-1>r-l+1){//reset left and right if find a longer palindrome
    		l=++left;
    		r=--right;
    	}
    	int []result={l,r};
    	return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.