最长公共子序列

1143. 最长公共子序列

leetcode 链接

思路：

动态规划

1.确定 dp 数组含义：dp[i][j] 表示长度为 i，j 的字符串的最大公共子序列的长度 dp[i][j]。

2.初始化 dp 数组，dp[i][0] = 0, dp[0][j] = 0。表示长度为 0 的字符串的最大公共子序列的长度为 0。

3.确定遍历方向，从前往后遍历。

4.确定转换方程，当 arr1[i - 1] === arr2[j - 1] 时，dp[i][j] = dp[i - 1][j - 1] + 1，当 arr1[i - 1] !== arr2[j - 1] 时，dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])。

5.确定结束条件，遍历到最后一个字符，返回 dp[lenT1][lenT2] 即可。

typescript 解法

function longestCommonSubsequence(text1: string, text2: string): number {
  // 确定dp数组含义：dp表示长度为i，j的字符串的最大公共子序列的长度dp[i][j]
  const lenT1: number = text1.length;
  const lenT2: number = text2.length;
  const arr1: string[] = text1.split("");
  const arr2: string[] = text2.split("");
  // 初始化dp数组为0
  const dp: number[][] = new Array(lenT1 + 1)
    .fill(0)
    .map(() => new Array(lenT2 + 1).fill(0));
  // 确定遍历方向
  for (let i: number = 1; i <= lenT1; i++) {
    for (let j: number = 1; j <= lenT2; j++) {
      if (arr1[i - 1] === arr2[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[lenT1][lenT2];
}

go 解法

func longestCommonSubsequence(text1 string, text2 string) int {
    // 确定dp数组含义，长度为i，和j的字符串的最长公共子序列长度为dp[i][j]
    lenT1 := len(text1)
    lenT2 := len(text2)
    dp := make([][]int, lenT1 + 1)
    // 初始化dp数组，长度为0的字符串的公共子序列长度为0
    for i := 0; i <= lenT1; i ++ {
        dp[i] = make([]int, lenT2 + 1)
    }
    // 确定遍历方向
    for i := 1; i <= lenT1; i ++ {
        for j := 1; j <= lenT2; j ++ {
            // 确定转换方程：当遇见相等的字符时，则最长公共子序列长度为dp[i - 1][j - 1] + 1,
            // 不相等则取dp[i - 1][j], dp[i][j - 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[lenT1][lenT2]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}