LeetCode 1143: Longest Common Subsequence (2D Dynamic Programming)

2026-03-17 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 1143DPString

Today we solve LeetCode 1143 - Longest Common Subsequence.

Source: https://leetcode.com/problems/longest-common-subsequence/

LeetCode 1143 longest common subsequence DP table diagram

English

Problem Summary

Given two strings text1 and text2, return the length of their longest common subsequence.

Key Insight

Define dp[i][j] as the LCS length between text1[0..i-1] and text2[0..j-1]. If current chars match, extend diagonal; otherwise keep the better value from top/left.

Optimal Algorithm (Step-by-Step)

1) Create a (m+1) x (n+1) DP table initialized to 0.
2) Iterate i=1..m and j=1..n.
3) If text1[i-1] == text2[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
4) Else set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
5) Answer is dp[m][n].

Complexity Analysis

Time: O(mn).
Space: O(mn).

Common Pitfalls

- Mixing 0-based string index with 1-based DP index.
- Forgetting base row/column as 0.
- Using diagonal update when chars do not match.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else if dp[i-1][j] > dp[i][j-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[m][n]
}

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = (int)text1.size(), n = (int)text2.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 (text1[i - 1] == text2[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];
    }
};

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[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]

var longestCommonSubsequence = function(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
};

中文

题目概述

给定两个字符串 text1 和 text2，返回它们最长公共子序列（LCS）的长度。

核心思路

定义 dp[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。若当前字符相等，取左上角 +1；否则取上方和左方的较大值。

最优算法（步骤）

1）创建 (m+1) x (n+1) 的 DP 表，初始为 0。
2）双层循环遍历 i=1..m、j=1..n。
3）若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
4）否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
5）最终答案是 dp[m][n]。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(mn)。

常见陷阱

- 字符串下标与 DP 下标错位（0-based vs 1-based）。
- 忘记初始化第 0 行和第 0 列为 0。
- 字符不相等时错误使用左上角转移。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else if dp[i-1][j] > dp[i][j-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[m][n]
}

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = (int)text1.size(), n = (int)text2.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 (text1[i - 1] == text2[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];
    }
};

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[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]

var longestCommonSubsequence = function(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
};