My Recursive DP Solution is getting a TLE. Can someone please help me understand the complexity of my solution?


  • 0
    S

    So I have been at this for a while. And I need help understanding the complexity of my approach. Also I looked around at other people's solutions and no one seems to have approached this from a recursive standpoint. Is there a reason why a recursive DP solution is not the best idea?

    import java.util.Hashtable;
    public class Solution {
        public class Pair {
            public int i; 
            public int j;
            public Pair(int i, int j) {
                this.i = i;
                this.j = j;
            }
        }
        public Pair helper(String s, int low, int high, Pair[][] history, int len, int strLow, int strHigh) {
            if(history[low][high]!=null) {
                if(strHigh - strLow + 1 == len + history[low][high].j - history[low][high].i + 1) 
                    return new Pair(strLow, strHigh); 
                else 
                    return history[low][high];
            }
            
            if(low==high || (low > high && len>0)) {
                return new Pair(strLow, strHigh); 
            }
    
            if(low>high) {
                return new Pair(-1, -1); 
            }
            
    
            Pair res = null;
            if(s.charAt(low)==s.charAt(high)) 
                res = helper(s, low+1, high-1, history, len+2, strLow, strHigh);
            
            if( res==null || (res.j - res.i  < high - low )) {
                Pair res1 = helper(s, low, high-1, history, 0, low, high-1);
                Pair res2 = helper(s, low+1, high, history, 0, low+1, high);
                Pair temp = (res1.j - res1.i >= res2.j - res2.i)? res1 : res2;
                res = (res!=null && res.j - res.i >= temp.j - temp.i)? res : temp;
            }
            history[low][high] = res;
            return history[low][high];
        }
        
        public String longestPalindrome(String s) {
            if(s.length() <=1) {
                return s;
            }
            Pair res = helper(s, 0, s.length()-1, new Pair[s.length()][s.length()] ,  0, 0 , s.length()-1);
            return s.substring(res.i, res.j + 1);
    
        }
    }
    

  • 1
    Y
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    S

    @yixuanwang.start Thank you! I appreciate it. I'll try and read up more on DP :)


Log in to reply
 

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