Time Cost

27min18s

Implementation

dp[i][j] represents the longest subsequence in the case when tail of text1 is index i and tail of text2 is index j. Use a 2D vector dp to avoid redundant calculation.

Code

• My Solution

  class Solution {
    int dp[1001][1001];
  public:
    int longestCommonSubsequence(string text1, string text2) {
        memset(dp, -1, sizeof(dp));
        return helper(text1, text2, text1.size() - 1, text2.size() - 1);
    }
      
    int helper(string &s1, string &s2, int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (dp[i][j] != -1) return dp[i][j];
          
        if (s1[i] == s2[j]) 
            return dp[i][j] = 1 + helper(s1, s2, i - 1, j - 1);
        return dp[i][j] = max(helper(s1, s2, i - 1, j), helper(s1, s2, i, j - 1));
    }
  };