Блог пользователя iharshit009

Автор iharshit009, 4 года назад, По-английски

I was doing a problem on Basic Memoization, Longest Common Subsequence( https://leetcode.com/problems/longest-common-subsequence/ )

I wrote a solution:

class Solution {
public:
    int lcs(int i, int j, string text1,string text2, vector<vector<int>>&dp){
        if( i>=text1.size() || j >= text2.size())
            return 0;
        if(dp[i][j] != -1)
            return dp[i][j];
        if(text1[i] == text2[j])
            return dp[i][j] = ( 1+ lcs(i+1 , j +1, text1, text2, dp));
        int left = lcs(i+1, j, text1, text2,dp);
        int right = lcs(i, j +1, text1, text2,dp);
        return dp[i][j] = max(left, right);
    }   
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>>dp(text1.size(), vector<int>(text2.size(), -1));
        return lcs(0,0,text1, text2, dp);
    }
};

Which seems to give TLE on 1/43 test cases, and 42 are passed

On the other side when I submitted this:

class Solution {
public:
    int lcs(int i, int j, string &text1,string &text2, vector<vector<int>>&dp){
        if( i>=text1.size() || j >= text2.size())
            return 0;
        if(dp[i][j] != -1)
            return dp[i][j];
        if(text1[i] == text2[j])
            return dp[i][j] = ( 1+ lcs(i+1 , j +1, text1, text2, dp));
        int left = lcs(i+1, j, text1, text2,dp);
        int right = lcs(i, j +1, text1, text2,dp);
        return dp[i][j] = max(left, right);
    }   
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>>dp(text1.size(), vector<int>(text2.size(), -1));
        return lcs(0,0,text1, text2, dp);
    }
};

It seems to run perfectly in all test cases

The difference in both is of Call by reference and Call by Value Does this create an issue with Time Complexity of an algorithm?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится