facebook code lab - longest palindrome - first writing

longestPalindrome1.java

/**
 * 
 */
/**
 * @author jchen
 *
 */
package test;

public class testing{
	
	public static void main(String[] args) {
	// TODO Auto-generated method stub

		String test = longestPalindrome("abb"); 
		System.out.print(test);
	}


	public static String longestPalindrome(String a) {
	    if(a==null)
	        return ""; 
	    int len = a.length(); 
	    
	   
	    int maxLength = 0; 
	    String res = ""; 
	    
	    // center aba style 
	    for(int i=0; i< len;i++)
	    {
	        String s1 = getPalindromeLenC(a, i); 
	        int newOne = s1.length(); 
	        boolean update = newOne > maxLength; 
	        maxLength = update? newOne : maxLength; 
	        res = update? s1 : res; 
	    }
	    
	    // abba style
	    for(int i=0; i< len; i++)
	    {
	        String s1 = getPalindromLenR(a,i); 
	        int newOne = s1.length(); 
	        boolean update = newOne > maxLength; 
	        maxLength = update? newOne : maxLength; 
	        res = update? s1 : res; 
	    }
	    
	    return res; 
	}
	
	/* abcba style, center position is char c */
	public static String getPalindromeLenC(String s, int index)
	{
	    int len = s.length(); 
	    
	    int span = 1; 
	    while((index + span) < len && (index-span) >=0)
	    {
	        if(s.charAt(index+span) == s.charAt(index-span))
	           span++; 
	        else
	           break; 
	    }
	    
	    return s.substring(index-span +1, index+span -1); 
	}
	
	/*abba style, center position is first b */
	public static String getPalindromLenR(String s, int index)
	{
	    int len = s.length(); 
	    
	    int begin =index; 
	    int end = index +1; 
	    
	    boolean hasOne = false; 
	    while(begin >= 0 && end < len)  // len, not len-1
	    {
	        if(s.charAt(begin) == s.charAt(end))
	        {
	            hasOne = true; 
	            begin --; 
	            end ++; 
	        } 
	        else
	          break; 
	    }
	    
	    return (hasOne)? s.substring(begin+1, end):""; 
	}
}

Practice notes:

1. String - compile error: string, Java String class, not string. Different from C#
2. String.substring(int beginIndex, endIndex), endIndex is exclusive <- understand exclusive meaning here: line 66, line 90
3. Java String [] operator - compiler error, using charAt() function
   4 . line 33 - 36 bug removal - use extra boolean update, since line 35 - update maxLength, so line 36 update boolean should not be used. Saved status
4. Two for loops can be merged into one loop
5. Design concern, use start pos and end pos, substring has O(n^2), but if only consider the center position of palindrome, only O(n) case.