2026/03/30

[LeetCode] 1143 Longest Common Subsequence 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
  int longestCommonSubsequence(string s1, string s2) {
    constexpr int SIZE = 1001;
    int dp[SIZE][SIZE] = {0};

    for (int i = 1; i <= s1.length(); i++) {
      for (int j = 1; j <= s2.length(); j++) {
        if (s1[i - 1] == s2[j - 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[s1.length()][s2.length()];
  }
};
Labels: