Description Link to heading

1143.longest-common-subsequence

Solution Link to heading

dp[i][j] denotes the length of longest common subsequence of first i characters of text1 and first j characters of text2:

  • if (text[i - 1] == text2[j - 1]), dp[i][j] = dp[i - 1][j - 1] + 1;
  • if (text[i - 1] != text2[j - 1]), dp[i][j] = max(dp[i - 1][j], dp[i][j - ]);

Code Link to heading 

#include <string>
#include <vector>
using std::string;
using std::vector;
class Solution {
  public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        int m = 0;
        int res = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    //dp[i][j] = max(dp[i - 1][j - 1] + 1, max(dp[i - 1][j], dp[i][1]));
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};