最长公共子序列

发表于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，1143. Longest Common Subsequence

先看题目描述

cn9nFP.png

大意就是给定两个字符串 text1 和 text2，求其最长公共子序列长度

算法和思路

动态规划

这题挺简单的，只要想到了动态规划，构建二维的状态方程，一下就可以解决

  • 状态方程：dp[i][j] 表示子串 text1[0：i - 1] 和子串 text2[0：j - 1] 的最长公共子序列长度
  • 状态转移方程：
    • 若 text1[i - 1] 和 text2[j - 1] 相等，则 dp[i][j] = dp[i - 1][j - 1] + 1
    • 否则，dp[i][j] = max{dp[i - 1][j]，dp[i][j - 1]}

设 text1 长度为 m，text2 长度为 n，最后返回 dp[m][n] 即可

算法源码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] cs1 = text1.toCharArray();
        char[] cs2 = text2.toCharArray();
        int m = cs1.length;
        int n = cs2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c = cs1[i - 1];
            for (int j = 1; j <= n; j++) {
                if (c == cs2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }
}