忍者算法

Appearance

最长公共子序列：寻找序列之间的共同密码 ​

大家好！今天我们要探讨一个在计算机科学、生物信息学和自然语言处理领域都有广泛应用的经典问题——最长公共子序列(LCS)。这是动态规划的又一个精彩应用，让我们一起来揭开它的奥秘！

🌟 子序列与子串：一字之差的概念转变 ​

首先，我们需要理解一个重要的区别：子序列与子串。

  • 子串：必须连续的字符序列。例如，"abc"的子串有"a"、"ab"、"bc"等。
  • 子序列：可以不连续，但必须保持原有顺序的字符序列。例如，"abc"的子序列有"a"、"b"、"c"、"ab"、"ac"、"bc"、"abc"。

这个看似微小的区别，却导致了解题思路的巨大变化！

🎯 问题描述：共同的遗传密码 ​

给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。

例如：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列。

🤔 从小例子开始思考 ​

让我们通过一个简单例子来理解这个问题：

text1 = "abcde"
text2 = "ace"

我们需要找出既出现在text1又出现在text2中的最长序列，并且字符顺序需保持一致。

检查所有可能的公共子序列：

  • "a"：✓ 长度为1
  • "c"：✓ 长度为1
  • "e"：✓ 长度为1
  • "ac"：✓ 长度为2
  • "ae"：✓ 长度为2
  • "ce"：✓ 长度为2
  • "ace"：✓ 长度为3

所以最长公共子序列是"ace"，长度为3。

💡 递归思路：自顶向下的分解 ​

我们可以从递归的角度思考这个问题。考虑两个字符串的最后一个字符：

  1. 如果它们相等，那么这个字符一定在最长公共子序列中，我们只需要找出剩余部分的最长公共子序列，然后加1。
  2. 如果它们不相等，那么最长公共子序列要么不包含text1的最后一个字符，要么不包含text2的最后一个字符，取这两种情况的较大值。

用递归表达：

LCS(i, j) = 表示text1[0...i]和text2[0...j]的最长公共子序列长度

如果text1[i] == text2[j]:
    LCS(i, j) = LCS(i-1, j-1) + 1
否则:
    LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

📝 动态规划解法：自底向上的构建 ​

递归思路会导致大量重复计算，我们可以使用动态规划来优化：

java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        
        // dp[i][j]表示text1[0...i-1]和text2[0...j-1]的LCS长度
        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];
    }
}

时间复杂度：O(m×n)，其中m和n分别是两个字符串的长度 空间复杂度：O(m×n)，需要一个二维数组存储中间结果

🎨 图解动态规划：可视化理解过程 ​

以text1 = "abcde", text2 = "ace"为例，我们来看看dp数组的填充过程：

   |   | a | c | e
---+---+---+---+---
   | 0 | 0 | 0 | 0
---+---+---+---+---
 a | 0 | 1 | 1 | 1
---+---+---+---+---
 b | 0 | 1 | 1 | 1
---+---+---+---+---
 c | 0 | 1 | 2 | 2
---+---+---+---+---
 d | 0 | 1 | 2 | 2
---+---+---+---+---
 e | 0 | 1 | 2 | 3

例如，当我们计算dp[3][2]时，表示"abc"和"ac"的LCS：

  • text1[3-1] = 'c'，text2[2-1] = 'c'，它们相等
  • 所以dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2
  • 意味着"abc"和"ac"的LCS长度为2，即"ac"

最终dp[5][3] = 3，表示"abcde"和"ace"的LCS长度为3。

💫 空间优化：滚动数组 ​

由于dp[i][j]只依赖于当前行和前一行的值，我们可以使用两个一维数组或者滚动一维数组来优化空间：

java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // 确保text1是较短的字符串，优化空间
        if (m > n) {
            return longestCommonSubsequence(text2, text1);
        }
        
        int[] dp = new int[n+1];
        
        for (int i = 1; i <= m; i++) {
            int prev = 0; // dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int curr = dp[j]; // 保存dp[i-1][j]
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]);
                }
                prev = curr; // 为下一次循环更新dp[i-1][j-1]
            }
        }
        
        return dp[n];
    }
}

时间复杂度：O(m×n) 空间复杂度：O(min(m,n))，只需要一个长度为较短字符串长度的数组

🔎 还原最长公共子序列 ​

有时我们不仅需要长度，还需要具体的最长公共子序列。可以通过回溯dp数组实现：

java
class Solution {
    public String getLCS(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        
        // 填充dp数组
        // ...省略与前面相同的代码...
        
        // 回溯构建LCS
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                lcs.insert(0, text1.charAt(i-1));
                i--;
                j--;
            } else if (dp[i-1][j] > dp[i][j-1]) {
                i--;
            } else {
                j--;
            }
        }
        
        return lcs.toString();
    }
}

🔀 最长公共子序列的变体问题 ​

LCS问题有许多有趣的变体：

  1. 最长公共子串：要求连续的公共部分
  2. 最短公共超序列：包含两个字符串所有字符的最短序列
  3. 编辑距离：将一个字符串转变为另一个的最少操作次数
  4. 最长递增子序列：单个序列中递增的最长子序列

每个变体都有其独特的应用场景和解决方案，但核心思想都与动态规划息息相关。

🌐 现实应用：从DNA到代码比较 ​

LCS在实际中有众多应用：

  • 生物信息学：比较DNA序列，寻找共同的遗传信息
  • 版本控制系统：比较文件变化，如Git的diff功能
  • 拼写检查：寻找错误单词与正确单词的共同部分
  • 语言学：比较不同语言中词汇的相似性

💯 LCS的本质：寻找不变量 ​

从算法的本质看，LCS是在寻找两个序列中的"不变量"——无论环境如何变化，这些元素始终按特定顺序出现。这种思想在计算机科学的许多领域都有体现：

  • 软件工程：识别重构前后代码的不变行为
  • 机器学习：提取数据中的稳定特征
  • 模式识别：在噪声中识别稳定模式

🎓 面试技巧与常见陷阱 ​

面试中关于LCS的常见问题：

  1. 初始化问题：dp数组的基础情况需要正确初始化
  2. 多个LCS：如何处理多个等长的最长公共子序列
  3. 空间优化：如何将空间复杂度降至O(n)
  4. 回溯构建：如何正确回溯得到实际的LCS

面试时，从简单的二维DP解法开始，再考虑空间优化，展示你的思维过程。

💡 解题思路总结 ​

解决LCS问题的关键步骤：

  1. 理解问题：明确子序列与子串的区别
  2. 定义状态：dp[i][j]表示什么
  3. 找出转移方程：当字符相等/不相等时如何转移
  4. 确定边界条件：空字符串的LCS为0
  5. 空间优化：从二维到一维的转变
  6. 实际应用：如何应用于实际问题

🤔 思考题 ​

如果我们有三个字符串，如何找到它们的最长公共子序列？这种情况下，动态规划的状态和转移方程会有什么变化？

作者：忍者算法
公众号：忍者算法

最长公共子序列问题是理解动态规划思想的一个绝佳例子，它展示了如何将复杂问题分解为重叠子问题，并通过自下而上的构建方式高效求解。掌握LCS，不仅能帮助我们解决算法题，更能培养我们寻找事物本质和不变量的思维方式！

#算法面试 #LeetCode #动态规划 #最长公共子序列 #字符串算法

🌉 LCS与其他算法的联系 ​

最长公共子序列是一个连接多种算法思想的桥梁。它与编辑距离、序列对齐、字符串匹配等问题紧密相连。理解LCS，就像掌握了一把开启多个算法领域的钥匙。

例如，LCS与编辑距离之间存在这样的关系：

编辑距离 = 字符串1长度 + 字符串2长度 - 2×LCS长度

当我们深入思考这个关系，就能发现两个问题的本质联系：LCS寻找的是需要保留的部分，而编辑距离关注的是需要修改的部分。同一个问题，两种视角！

在未来算法学习的道路上，这种发现问题之间联系的能力将帮助我们构建更加系统化的算法知识网络，而不仅仅是孤立地解决单个问题。