Optimized Java search and expand solution.


  • 0
    A

    Your standard Search and Expand with a twist.
    Search and Expand like you see in many solutions with:
    expand(s, i, i);
    expand(s, i, i+1);
    These don't deal with repeating characters very well, like: "baaaaaab"
    it would try index 0 to 7. for index 1 to 6 it would repeatedly try to expand and fail, sometimes iterating pretty far before detecting failure. We can greatly improve that and reduce our "expands" call to 1 instead of 2.
    Instead upon index 1, scan forward while charAt(index+1) == charAt(index).
    Now we have our left and right bounds to expand from.
    So now we try:
    expands(s,l,r) where l=index, and r=the rightmost consecutive matching character.

    This proves to be much much faster in repeating character cases.

    Please forgive the untidiness.

    class Solution {
    	public String longestPalindrome( String s ) {
    		if (s == null)
    			return "";
    		int len = s.length();
    		if (len < 2)
    			return s;
    		if (len < 3) {
    			if (s.charAt( 0 ) == s.charAt( 1 )) {
    				return s;
    			} else {
    				return s.substring( 0, 1 );
    			}
    		}
    		int ll = 0;
    		int lr = 0;
    
    		int[] out = new int[2];
    		for (int l = 0; l < s.length() - 1; l++) {
    			// advance the right cursor while the character matches the prev
    			// this allows us to not double, triple+ count duplicate letter sequences
    			// it also allows us to deal with the case where the adjacent letter or letters are equal in the center of a palindrome
    			char prev = l > 0 ? s.charAt( l - 1 ) : '\0';
    			char c = s.charAt( l );
    			int r = l;
    			if (c != prev) {
    				while (r < s.length() - 1 && s.charAt( r ) == c) {
    					r++;
    				}
    				if (s.charAt( r ) != c)
    					r--;
    			}
    
    			// expand outward from l and r
    			expand( s, l, r, out );
    			if (lr - ll < out[1] - out[0]) {
    				ll = out[0];
    				lr = out[1];
    			}
    			l = r;
    		}
    
    		return s.substring( ll, lr + 1 );
    	}
    
    	private void expand( String s, int l, int r, int[] out ) {
    		while (l > 0 && r < s.length() - 1 && s.charAt( l ) == s.charAt( r )) {
    			l--;
    			r++;
    		}
    		if (s.charAt( l ) != s.charAt( r )) {
    			l++;
    			r--;
    		}
    		out[0] = l;
    		out[1] = r;
    	}
    

Log in to reply
 

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