1143. 最长公共子序列（中等）

Blind 75 › 1143. 最长公共子序列（中等） （第 12 章）
文章工具

题目

给定两个字符串 text1 和 text2，返回它们的最长公共子序列（Longest Common Subsequence，LCS）的长度。如果两者没有公共子序列，返回 0。

“子序列”指：从原串里不改变相对顺序地删掉若干字符（也可以一个都不删）后得到的新串。它不要求连续，因此与“子串 / 子数组”不同。

自造示例：

  • text1 = "abcde"，text2 = "ace" → 返回 3，最长公共子序列是 "ace"。
  • text1 = "abcde"，text2 = "bdf" → 返回 2，最长公共子序列可以是 "bd"。
  • text1 = "abc"，text2 = "xyz" → 返回 0，两者没有任何公共子序列。

约束：两个字符串的长度都在 1 ~ 1000，字符均为小写字母。

思路：先暴力，再看“重叠”

一句话本质：比较两个串的“当前尾巴”，能配对的字符直接拿下，配不上的就淘汰其中一边，逐步缩小问题。

最直白的做法：枚举 text1 的全部子序列，再去 text2 里验证它是否也是 text2 的子序列。长度为 m 的串有 2^m 个子序列，验证每个又要 O(n)；当 m = 1000 时，这完全是天文数字，不可行。

它慢的根本原因是重叠子问题。比如 text1 = "cbat"，无论你先删掉 c 还是先删掉 a，最后都会落到同一个子问题“bat 与 text2 的 LCS 是多少”，而暴力枚举会把它反复重算。

关键观察：LCS 有最优子结构。设 dp[i][j

🔒

本篇为付费内容

您已阅读试读部分，购买后即可解锁全文。

⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。