目录

1143_最长公共子序列

题目

leetcode # 1143. 最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。 例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 输入:text1 = “abcde”, text2 = “ace” 输出:3
解释:最长公共子序列是 “ace”,它的长度为 3。

分析

和{%post_link 工作/100_计科基础/数据结构与算法/leetcode/最长重复子数组_718%}很像,不同之处是可以不连续,所以当A[i]不等于B[j] 则f[i][j] = max(f[i-1][j], f[i][j-1]);

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    public static int longestCommonSubsequence(String text1, String text2) {
        int[][] f = new int[text1.length()+1][text2.length() + 1];
        for (int i = 0; i < text1.length() + 1; i++) {
            f[i][0] = 0;
        }
        for (int j = 0; j < text2.length() + 1; j++) {
            f[0][j] = 0;
        }
        for (int i = 0; i < text1.length(); i++) {
            for (int j = 0; j < text2.length(); j++) {
                // f[i][j]需要在数组下标的基础上+1, A[0],B[0]相当于f[1][1]
                if (text1.charAt(i) == text2.charAt(j)) {
                    f[i + 1][j + 1] = f[i][j] + 1;
                } else {
                    f[i + 1][j + 1] = Math.max(f[i+1][j], f[i][j+1]);
                }
            }
        }
        return f[text1.length()][text2.length()];
    }