Optimized n-square solution in Java


  • 7
    A

    Maybe this is a "greedy" way to find solution:
    len = length of s;
    Try to find a palindrome of length = len,
    then length len-1, len-2, ...
    Whenever we find one, this is the largest one, and we don't need to check the rest.

    /**
     * when i see "longest", i think of optimization or greedy.
     * don't want to try every possibility and then return
     * longest one, that will be guaranteed n-square.
     * 
     * try len=s.lenth(),
     * then len-1, len-2, until len=0.
     * whenever i find a palindrome of length len, this is the longest one.
     */
    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int len = s.length();
        while (len >= 0) {
            for (int i = 0; i + len - 1 < chars.length; i++) {
                int left = i;
                int right = i + len - 1;
                boolean good = true;
                while (left < right) {
                    if (chars[left] != chars[right]) {
                        good = false;
                        break;
                    }
                    left++;
                    right--;
                }
                if (good)
                    return s.substring(i, i + len);
            }
            --len;
        }
        
        return "";
    }

  • 0
    X

    beautiful optimization,it is faster than dp


  • 0
    N

    This is an n-cube solution
    The number of operations required is sum{i * (n+1-i)} from i=1 through n


Log in to reply
 

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