问题

求两个字符串的最长公共子序列(不是子串)，最长公共子序列（Longest Common Subsequence，简称 LCS）。
示例：
输入: str1 = “abcde”, str2 = “ace”
输出: 3
解释: 最长公共子序列是 “ace”，它的长度是 3

思路

1、暴力构造两个字符串所有子序列，再循环比较。时间复杂度最长公共子序列 - 图1，时间复杂度太高。
2、发现问题符合独具有立子问题结构：
最长公共子序列 - 图2表示 s1[0..i] 与 s2[0..j] 的最长公共子序列，那么有如下状态转移方程
最长公共子序列 - 图3
据此，我们可以写出代码

代码

自顶向下：

  1. pub fn longest_common_subsequence_v3(text1: String, text2: String) -> i32 {
  2.     Self::longest_common_subsequence_recurse(text1.as_bytes(), text2.as_bytes())
  3. }
  5. fn longest_common_subsequence_recurse(s1: &[u8], s2: &[u8]) -> i32 {
  6.     if s1.len() == 0 || s2.len() == 0 {
  7.         return 0;
  8.     }
  10.     if s1[s1.len() - 1] == s2[s2.len() - 1] {
  11.         Self::longest_common_subsequence_recurse(&s1[0..s1.len() - 1], &s2[0..s2.len() - 1]) + 1
  12.     } else {
  13.         std::cmp::max(Self::longest_common_subsequence_recurse(&s1[0..s1.len() - 1], s2),
  14.             Self::longest_common_subsequence_recurse(s1, &s2[0..s2.len() - 1]))
  15.     }
  16. }

自顶向下递归对大量重复子问题重复求解，效率低，可以用记忆化存储保存子问题答案，提高效率
自顶向下优化：

  1. pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
  2.     // 保存子问题答案
  3.     let mut memorized = HashMap::new();
  5.     Self::longest_common_subsequence_recurse(text1.as_bytes(), text2.as_bytes(), &mut memorized)
  6. }
  8. fn longest_common_subsequence_recurse(s1: &[u8], s2: &[u8], memorized: &mut HashMap<(usize, usize), i32>) -> i32 {
  9.     if s1.len() == 0 || s2.len() == 0 {
  10.         return 0;
  11.     }
  13.     // 如果该问题已求解，直接返回
  14.     if let Some(len) = memorized.get(&(s1.len(), s2.len())) {
  15.         return *len;
  16.     }
  18.     let res;
  19.     if s1[s1.len() - 1] == s2[s2.len() - 1] {
  20.         res = Self::longest_common_subsequence_recurse(&s1[0..s1.len() - 1], &s2[0..s2.len() - 1], memorized) + 1
  21.     } else {
  22.         res = std::cmp::max(Self::longest_common_subsequence_recurse(&s1[0..s1.len() - 1], s2, memorized),
  23.             Self::longest_common_subsequence_recurse(s1, &s2[0..s2.len() - 1], memorized))
  24.     }
  26.     // 保存子问题答案
  27.     memorized.insert((s1.len(), s2.len()), res);
  28.     return res;
  29. }

自底向上：

pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
    let m = text1.len();
    let n = text2.len();
    let s1 = text1.as_bytes();
    let s2 = text2.as_bytes();
    // 二维dp数组，保存状态
    let mut dp = vec![vec![0;n + 1];m + 1];
    for i in 1..=m{
        for j in 1..=n{
            if s1[i-1] == s2[j-1]{
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = std::cmp::max(dp[i][j-1], dp[i-1][j]);
            }
        }
    }

    dp[m][n]
}

自底向上优化，压缩dp数组：

/// 发现二维dp数组，每次生成下一行数据只需要该位置上一行和该行左边的值，所以可以优化成一维数组
pub fn longest_common_subsequence_v2(text1: String, text2: String) -> i32 {
    let m = text1.len();
    let n = text2.len();
    let s1 = text1.as_bytes();
    let s2 = text2.as_bytes();
    // n 列
    let mut dp = vec![0;n + 1];
    // 相当于dp[i-1][j]
    let mut temp;
    for i in 1..=m{
        // 相当于dp[i-1][j-1]
        let mut last = 0;
        for j in 1..=n{
            // 此时dp[j]相当于dp[i-1][j]
            temp = dp[j];
            if s1[i-1] == s2[j-1] {
                dp[j] = last + 1;
            } else {
                dp [j] = std::cmp::max(temp, dp[j-1]);
            }
            last = temp;
        }
    }

    dp[n]
}