LeetCode - LCS Series

LeetCode - LCS Series

LAVI
  2026-05-07 2026-05-07 Created   2026-05-07 2026-05-07 Updated      

Medium

1143. Longest Common Subsequence 1035. Uncrossed Lines 583. Delete Operation for Two Strings

我的另一篇文章有解說各種 LIS & LCS 的解題思路，可以參考看看：

Algorithm - DP LIS and LCS

1143. Longest Common Subsequence

題目

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters, can be none, deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters.

解題思路

這題是經典 LCS 題
LCS 是 Longest Common Subsequence，也就是最長共同子序列

  • DP 定義：

    • dp[i][j]：text1 前 i 個字元和 text2 前 j 個字元的 LCS 長度

  • 初始化：

    • dp[0][j] = 0
    • dp[i][0] = 0
    • 只要其中一個字串是空字串，LCS 長度就是 0

  • 狀態轉移：

    • 如果 text1[i - 1] == text2[j - 1]

      • 代表這兩個字元相同
      • 這個字元可以加入共同 subsequence
      • dp[i][j] = dp[i - 1][j - 1] + 1

    • 如果 text1[i - 1] != text2[j - 1]

      • 代表這兩個字元不能一起選
      • 可以選擇不選 text1[i - 1]
      • 或是不選 text2[j - 1]
      • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

  • 最後答案為：
    dp[m][n]

Solution Code

Time Complexity
O(m × n)

Space Complexity
O(m × n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // text1 前 i 個字元 和 text2 前 j 個字元的 LCS 長度
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) { // 兩個字元相同
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 代表這個字元可以加入共同 subsequence
                } else { // 代表這兩個字元不能一起選
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 不選 text1[i - 1] 或不選 不選 text2[j - 1]
                }
            }
        }

        return dp[m][n];
    }
};

1035. Uncrossed Lines

題目

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2, in the order they are given, on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

  • nums1[i] == nums2[j]
  • the line we draw does not intersect any other connecting non-horizontal line

Note that a connecting line cannot intersect even at the endpoints, i.e., each number can only belong to one connecting line.

Return the maximum number of connecting lines we can draw in this way.

Example 1

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2] = 2 to nums2[1] = 2.

Example 2

Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

Example 3

Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2

Constraints

  • 1 <= nums1.length, nums2.length <= 500
  • 1 <= nums1[i], nums2[j] <= 2000

解題思路

這題本質上就是 LCS
因為線不能交叉，代表選到的數字順序不能改變

  • 如果 nums1[i-1] == nums2[j-1]

    • 代表這兩個數字可以連線
    • 並且可以接在前面的最佳答案後面

  • DP 定義：

    • dp[i][j]：nums1 前 i 個數字和 nums2 前 j 個數字，最多可以畫幾條不交叉的線

  • 初始化：

    • dp[0][j] = 0
    • dp[i][0] = 0
    • 只要其中一個 array 沒有數字，就無法畫線

  • 狀態轉移：

    • 如果 nums1[i-1] == nums2[j-1]

      • dp[i][j] = dp[i-1][j-1] + 1

    • 否則：

      • 不能把這兩個數字連起來
      • 選擇不看 nums1[i-1]
      • 或是不看 nums2[j-1]
      • dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  • 最後答案為：
    dp[m][n]

Solution Code

Time Complexity
O(m × n)

Space Complexity
O(m × n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();

        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                if(nums1[i-1] == nums2[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[m][n];
    }
};

583. Delete Operation for Two Strings

題目

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example 1

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2

Input: word1 = "leetcode", word2 = "etco"
Output: 4

Constraints

  • 1 <= word1.length, word2.length <= 500
  • word1 and word2 consist of only lowercase English letters.

解題思路

這題可以轉成 LCS
目標是讓兩個字串最後變成一樣

  • 如果保留兩個字串的最長共同子序列

    • 其他不在 LCS 裡的字元都刪掉
    • 就可以讓兩個字串變成相同

  • 所以先求 word1 和 word2 的 LCS 長度

  • DP 定義：

    • dp[i][j]：word1 前 i 個字元和 word2 前 j 個字元的 LCS 長度

  • 狀態轉移：

    • 如果 word1[i-1] == word2[j-1]

      • 代表這個字元可以保留
      • dp[i][j] = dp[i-1][j-1] + 1

    • 否則：

      • 選擇不看 word1[i-1]
      • 或是不看 word2[j-1]
      • dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  • 假設 LCS 長度是 dp[m][n]

    • word1 要刪掉的字元數是：
      m - dp[m][n]
    • word2 要刪掉的字元數是：
      n - dp[m][n]

  • 最後答案為：
    (m - dp[m][n]) + (n - dp[m][n])

Solution Code

Time Complexity
O(m × n)

Space Complexity
O(m × n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                if(word1[i-1] == word2[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 (m - dp[m][n]) + (n - dp[m][n]);
    }
};

Conclusion

這幾題都是 LCS 的延伸題

  • 1143 Longest Common Subsequence

    • 最標準的 LCS 題
    • 判斷兩個字串的最長共同子序列長度

  • 1035 Uncrossed Lines

    • array 版本的 LCS
    • 因為線不能交叉，所以選到的數字順序不能改變
    • 本質就是找兩個 array 的最長共同子序列

  • 583 Delete Operation for Two Strings

    • LCS 的應用題
    • 保留兩個字串共同的 LCS
    • 其他字元全部刪掉
    • 最少刪除次數就是：
      (word1.length - LCS) + (word2.length - LCS)

LCS 題型的核心通常是：
比較兩個序列的前綴狀態

如果目前字元相同，就從左上角轉移：
dp[i][j] = dp[i-1][j-1] + 1

如果目前字元不同，就從上方或左方取最大值：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

On this page
LeetCode - LCS Series
  1. 1143. Longest Common Subsequence
  2. 題目
  3. 解題思路
  4. Solution Code
  5. 1035. Uncrossed Lines
  6. 題目
  7. 解題思路
  8. Solution Code
  9. 583. Delete Operation for Two Strings
  10. 題目
  11. 解題思路
  12. Solution Code
  13. Conclusion