Be careful of substring() function. Java O(n^2) may got TLE.


  • 9
    D

    My TLE code:

    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) {
            return s;
        }
        int len = s.length();
        String subString = "";
        // palindrome[i][j] : substring(i,j) is palindrome or not?
        boolean[][] palindrome = new boolean[len][len];
        // calculate palindrome[][]
        for(int i=0;i<len;i++) {
            palindrome[i][i] = true;
        }
        for(int i=1;i<len;i++) {
            if(s.charAt(i-1) == s.charAt(i)) {
                palindrome[i-1][i] = true;
                subString = s.substring(i-1, i+1);
            }
        }
        for(int k=2;k<len;k++) {
            for(int i=0;i+k<len;i++) {
                int j = i+k;
                if(s.charAt(i) == s.charAt(j) && palindrome[i+1][j-1]) {
                    palindrome[i][j] = true;
                    subString = s.substring(i, j+1);
                }
            }
        }
        return subString;
    }
    

    I find that substring is time-consuming.
    So My Accepted code is here:

    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) {
            return s;
        }
        int len = s.length();
        int start = 0, end = 0;
        // palindrome[i][j] : substring(i,j) is palindrome or not?
        boolean[][] palindrome = new boolean[len][len];
        // length = 1
        for(int i=0;i<len;i++) {
            palindrome[i][i] = true;
        }
        // length = 2
        for(int i=1;i<len;i++) {
            if(s.charAt(i-1) == s.charAt(i)) {
                palindrome[i-1][i] = true;
                start = i-1; end = i+1;
            }
        }
        // length = k (k=2..len)
        for(int k=2;k<len;k++) {
            for(int i=0;i+k<len;i++) {
                int j = i+k;
                if(s.charAt(i) == s.charAt(j) && palindrome[i+1][j-1]) {
                    palindrome[i][j] = true;
                    start = i; end = j+1;
                }
            }
        }
        return s.substring(start, end);
    }
    

    I hope I can help you!


  • 0
    M

    Thank you for your help. I modified my code with less subString and it was acceped. Here is my code.
    /**
    *
    *
    * @param s
    * @return
    */
    public String longestPalindrome(String s) {

    	String result = null;
    
    	for (int i = 0; i < s.length(); i++) {
    
    		String oddString = this.subPalindromeString(s, i, i);
    		String evenString = null;
    
    		if (i != s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
    			evenString = this.subPalindromeString(s, i, i + 1);
    		}
    
    		if (evenString != null) {
    			if (evenString.length() > oddString.length()) {
    				oddString = evenString;
    			}
    		}
    
    		if (result != null) {
    			result = result.length() < oddString.length() ? oddString
    					: result;
    		} else {
    			result = oddString;
    		}
    	}
    
    	return result;
    }
    
    /**
     *
     * @param s
     * @param startIndex
     *            中心节点的起始位置
     * @param endIndex
     *            中心节点的结束位置
     * @return
     */
    public String subPalindromeString(String s, int startIndex, int endIndex) {
    	String result = s.substring(startIndex, endIndex + 1);
    
    	int range = 1;
    
    	boolean change = false;
    
    	while (startIndex - range >= 0 && endIndex + range < s.length()) {
    
    		// String subString =
    		if (s.charAt(startIndex - range) == s.charAt(endIndex + range)) {
    			change = true;
    			range++;
    		} else {
    			break;
    		}
    	}
    	if (change) {
    		result = s.substring(startIndex - range + 1, endIndex + range);
    	}
    	return result;
    }

  • 1
    D

    Seems a bit overly complicated, there's really no need for a boolean matrix.

    I think a simple "expand around center" algorithm is sufficient.

    Here's my solution, ran in 269 ms:

    public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        String longest = s.substring(0, 1);  // a single char itself is a palindrome
        for (int i = 0; i < n - 1; i++) {
          String p1 = expandAroundCenter(s, i, i);
          if (p1.length() > longest.length())
            longest = p1;
     
          String p2 = expandAroundCenter(s, i, i+1);
          if (p2.length() > longest.length())
            longest = p2;
        }
        return longest;
      }
        
    
    
    public String expandAroundCenter(String s, int c1, int c2) {
        int l = c1, r = c2;
        int n = s.length();
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;  
        }
        return s.substring(l + 1  , r );
    }
    

    }


  • 1
    M

    i think the boolean matrix solution is inspired by dynamic programming, also a good one.


Log in to reply
 

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