最长公共子序列

题目要求

给定两个字符串 text1 和 text2，目标是找到这两个字符串之间的最长公共子序列（Longest Common Subsequence, LCS）的长度。公共子序列指的是两个字符串中都出现的、并且在每个字符串内部字符顺序相同的序列。这个序列不需要在原字符串中连续出现。如果没有公共子序列，则返回长度为 0。

解题思路

解决这个问题的经典方法是使用动态规划（Dynamic Programming, DP）。动态规划是一种算法思想，它将一个问题分解为相似的子问题，通过解决子问题来递推得到最终问题的解。

  1. 初始化 DP 表格：创建一个二维数组 dp，其中 dp[i][j] 表示 text1 中前 i 个字符和 text2 中前 j 个字符的最长公共子序列的长度。由于子序列的长度可以为 0，所以 dp 表的大小应该是 (len(text1) + 1) x (len(text2) + 1)，并且初始化第一行和第一列为 0，因为任何字符串与空字符串的最长公共子序列长度都是 0。

  2. 填充 DP 表格：遍历两个字符串，对于 dp 表中的每个元素 dp[i][j]，有两种情况：

    • 如果 text1[i - 1] == text2[j - 1]，说明这两个字符匹配，那么 dp[i][j] 应该是 dp[i - 1][j - 1] 加 1，因为我们找到了一个额外的匹配字符。
    • 如果 text1[i - 1] != text2[j - 1]，说明这两个字符不匹配，那么 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 中的较大值，因为我们要找到最长的子序列，所以我们需要考虑不包含 text1[i - 1] 或不包含 text2[j - 1] 的情况。

  3. 遍历 DP 表格：从 dp[1][1] 开始，按行或按列遍历整个表格，根据上述规则填充每个 dp[i][j]。

  4. 返回结果：最终 dp[len(text1)][len(text2)] 将包含 text1 和 text2 的最长公共子序列的长度，这就是我们要找的答案。

通过这种方法，我们可以确保所有的子问题都被解决，并且每个子问题只解决一次，最终得到的解是最优的。

Golang 版本

package main

import (
	"fmt"
	"math"
)

// longestCommonSubsequence function calculates the length of the longest common subsequence
func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	// Create a DP table with extra row and column for base case (empty string)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// Fill the DP table
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				// If characters match, take diagonal value and add 1
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				// If characters don't match, take the max value from left or top cell
				dp[i][j] = int(math.Max(float64(dp[i-1][j]), float64(dp[i][j-1])))
			}
		}
	}

	// The bottom-right cell contains the length of LCS
	return dp[m][n]
}

func main() {
	text1 := "abcde"
	text2 := "ace"
	fmt.Println("The length of the longest common subsequence is:", longestCommonSubsequence(text1, text2))
}

这段代码定义了一个函数 longestCommonSubsequence，它接受两个字符串 text1 和 text2 作为输入，并返回它们之间的最长公共子序列的长度。主函数 main 中提供了两个示例字符串，并打印出了它们的最长公共子序列长度。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

// Function to find the length of the longest common subsequence
int longestCommonSubsequence(std::string text1, std::string text2) {
    int m = text1.length(), n = text2.length();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));

    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] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    std::string text1 = "abcde";
    std::string text2 = "ace";
    std::cout << "The length of the longest common subsequence is: "
              << longestCommonSubsequence(text1, text2) << std::endl;
    return 0;
}

这段 C++代码实现了一个函数 longestCommonSubsequence，它计算两个给定字符串 text1 和 text2 的最长公共子序列的长度。在 main 函数中，我们定义了两个示例字符串，并输出了它们的最长公共子序列的长度。

Python 版本

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    # Create a DP table with an extra row and column for the base case (empty string)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill the DP table
    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])

    # The bottom-right cell contains the length of the LCS
    return dp[m][n]

# Example usage
text1 = "abcde"
text2 = "ace"
print("The length of the longest common subsequence is:", longest_common_subsequence(text1, text2))

这段 Python 代码定义了一个函数 longest_common_subsequence，它接受两个字符串 text1 和 text2 作为输入，并返回它们之间的最长公共子序列的长度。在示例用法中，我们定义了两个字符串，并打印出了它们的最长公共子序列的长度。

Java 版本

public class LCS {
    // Function to find the length of the longest common subsequence
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int 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];
    }

    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println("The length of the longest common subsequence is: " + longestCommonSubsequence(text1, text2));
    }
}

这段 Java 代码定义了一个名为 LCS 的类，其中包含一个静态方法 longestCommonSubsequence，用于计算两个字符串 text1 和 text2 的最长公共子序列的长度。在 main 方法中，我们提供了两个示例字符串，并打印出了它们的最长公共子序列的长度。

Rust 版本

fn longest_common_subsequence(text1: &str, text2: &str) -> usize {
    let m = text1.len();
    let n = text2.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    let text1_bytes = text1.as_bytes();
    let text2_bytes = text2.as_bytes();

    for i in 1..=m {
        for j in 1..=n {
            if text1_bytes[i - 1] == text2_bytes[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::cmp::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    dp[m][n]
}

fn main() {
    let text1 = "abcde";
    let text2 = "ace";
    println!(
        "The length of the longest common subsequence is: {}",
        longest_common_subsequence(text1, text2)
    );
}

这段 Rust 代码定义了一个函数 longest_common_subsequence，它接受两个字符串切片 text1 和 text2 作为参数，并返回它们的最长公共子序列的长度。在 main 函数中，我们定义了两个示例字符串，并打印出了它们的最长公共子序列的长度。

总结

上述解法采用了动态规划（Dynamic Programming, DP）的方法来解决最长公共子序列（Longest Common Subsequence, LCS）问题。无论是在 C++、Python、Java 还是 Rust 语言中，核心算法的逻辑是相同的，主要步骤如下：

  1. 初始化一个二维数组 dp，其大小为 (m+1) x (n+1)，其中 m 和 n 分别是输入字符串 text1 和 text2 的长度。dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。

  2. 遍历两个字符串的每个字符，对于 dp 数组中的每个元素 dp[i][j]：

    • 如果 text1 的第 i 个字符和 text2 的第 j 个字符相同，那么 dp[i][j] 就是 dp[i-1][j-1] 加上这两个匹配字符构成的子序列的长度，即 dp[i][j] = dp[i-1][j-1] + 1。
    • 如果不相同，那么 dp[i][j] 就是 dp[i-1][j] 和 dp[i][j-1] 中的较大值，即不包含 text1 的第 i 个字符或不包含 text2 的第 j 个字符的最长公共子序列的长度。

  3. 继续填充 dp 数组，直到遍历完所有字符。

  4. dp[m][n] 就是最终的结果，即 text1 和 text2 的最长公共子序列的长度。

这种方法的时间复杂度和空间复杂度都是 O(mn)，其中 m 和 n 是两个字符串的长度。动态规划是解决此类问题的经典方法，因为它将问题分解为子问题，并存储子问题的解，避免了重复计算。