3
\$\begingroup\$

I am trying to solve the Longest Palindromic Substring problem on LeetCode, and I have come up with a DP solution pasted below:

public class Solution {
    String      string;
    boolean[][] visited;
    String[][]  results;

    private boolean isPalindrome(String s){
        String test = new StringBuilder(s).reverse().toString();
        if(test.equals(s)) return true; else return false;
    }

    private String maxLengthString(String... args){
        String result = new String();
        for(String arg:args){
            if(arg.length() > result.length()) result = arg;
        }
        return result;
    }

    private String findLongestPalindrome(int start,int end){
        if(start >= end) return new String();
        else if(start >= string.length() || start < 0) return new String();
        else if(end <= 0 || end > string.length()) return new String();
        else{
            if(visited[start][end-1] == true) return results[start][end-1];
            String result = new String();
            if(this.isPalindrome(string.substring(start,end)))
                result = maxLengthString(string.substring(start,end),
                                        findLongestPalindrome(start+1,end),
                                        findLongestPalindrome(start,end-1));
            else result = maxLengthString(findLongestPalindrome(start+1,end),
                                          findLongestPalindrome(start,end-1));
            visited[start][end-1] = true;
            results[start][end-1] = result;
            return result;
        }
    }

    public String longestPalindrome(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function

        string = s;
        visited = new boolean[s.length()][s.length()];
        results = new String[s.length()][s.length()];

        return findLongestPalindrome(0,s.length());
    }
}

The algorithm is quite straightforward, but the online judge complains about it not being efficient enough. I am just wondering if this algorithm is slow by nature (in which case I have to find another algorithm) or if it's something about my implementation.

\$\endgroup\$

migrated from stackoverflow.com Aug 6 '13 at 11:15

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ Also, it's probably slow because of the recursion. \$\endgroup\$ – But I'm Not A Wrapper Class Aug 2 '13 at 13:12
  • \$\begingroup\$ I see you are using a recursive approach. Have you tried to create an iterative solution and compare the results? \$\endgroup\$ – bblincoe Aug 2 '13 at 13:13
  • \$\begingroup\$ @bblincoe I will try later \$\endgroup\$ – dorafmon Aug 2 '13 at 13:16
  • 1
    \$\begingroup\$ @Bohemian I'd imagine, to become efficient enough, it would require a fundamentally different approach, i.e. basically a complete rewrite. Wouldn't this be beyond the scope of Code Review? UPDATE - Well, the question doesn't actually seem to be asking about a different approach, just why it's slow, so it may be fine for there, I'm not sure. \$\endgroup\$ – Dukeling Aug 2 '13 at 14:53
3
\$\begingroup\$

The proper way to solve it is to use a profiler to determine where the bottlenecks are, but by inspection, your search tree is at least twice the size it has to be and you will always expand the entire tree rather than terminating when you can.

if(this.isPalindrome(string.substring(start,end)))
            result = maxLengthString(string.substring(start,end),
                                    findLongestPalindrome(start+1,end),
                                    findLongestPalindrome(start,end-1));
        else result = maxLengthString(findLongestPalindrome(start+1,end),
                                      findLongestPalindrome(start,end-1));

if this.isPalindrome is true, then there is no way that findLongestPalindrome(start+1,end) or (start,end-1) could be longer. Rewriting this gives:

if(this.isPalindrome(sting.substring(start,end)))
    result = string.substring(start,end)
else
    ...
\$\endgroup\$
  • \$\begingroup\$ In the worst case it doesn't help at all \$\endgroup\$ – pkacprzak Aug 2 '13 at 13:21
3
\$\begingroup\$

Why is it slow?

The input string S can be up to 1000 characters.

Your DP solution considers all \$\mathcal{O}(|S|^2)\$ substrings of S and you're checking for each of these substrings, if it is a palindrome, in linear time in terms of the length of this substring.

Faster solutions

You can do it easily in \$\mathcal{O}(|S|^2)\$ using a polynomial hashing technique.

There are of course more sophisticated and linear solutions based on the famous Manacher algorithm.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.