Longest Palindromic Subsequence problem:

C :

class Solution {

public:

vector<vector<int>> dp;

Solution(){
    dp = vector<vector<int>>(1001, vector<int>(1001, -1));
}
int lps(string s, int i, int j){
    if(i == j)
        return 1;

    if(i>j)
        return 0;

    if(dp[i][j] != -1)
        return dp[i][j];
   
    if(s[i] == s[j])
        return dp[i][j]= 2   lps(s, i 1, j-1);
    else
        return dp[i][j]= max(lps(s,i 1,j), lps(s,i,j-1));
}

int longestPalindromeSubseq(string s) {
    return lps(s, 0, s.size()-1);
}

};

Gives TLE

Python code:

class Solution(object):

def lps(self, s, i, j, dp):
    if i == j:
        return 1
    if i> j:
        return 0
    
    if dp[i][j] != -1:
        return dp[i][j];
    
    if s[i] == s[j]:
        dp[i][j]= 2   self.lps(s, i 1, j-1, dp)
    else:
        dp[i][j]= max(self.lps(s, i 1, j, dp), self.lps(s, i, j-1, dp))
        
    return dp[i][j]
    
def longestPalindromeSubseq(self, s):
    dp = [[-1 for x in range(len(s))] for y in range(len(s))]
    ans= self.lps(s, 0, len(s) -1, dp)
    return ans

Passes all the test cases in leetcode. Can anyone please help me understand this behavior?

Thanks in advance.

CodePudding user response：

In C version you are passing string by value in function.(i.e. a new copy of string is made a each function call).

In python version since strings by default are immutable they are passed by reference.

So to make your code work in C just do int lps(string& s, int i, int j)

string &s here ensures that string get passed by reference.