java - 最长公共(public)子序列算法讲解

Question

于是最长公共(public)子序列问题的伪代码如下。

longest-common-subsequence(s1, s2):

If the strings begin with the same letter c, the result to return is cplus the longest common subsequence between the rest of s1 and s2(that is, s1 and s2 without their first letter). For example, thelongest subsequence between "hollow" and "hello" is an "h" plus thelongest subsequence found between "ollow" and "ello".

Otherwise, ifthe strings do not begin with the same letter, return the longer ofthe following two: The longest common subsequence between s1 and therest of s2 (s2 without its first letter), The longest commonsubsequence between the rest of s1 (s1 without its first letter) ands2. For example, longest-common-subsequence("ollow", "ello") is thelonger of longest-common-subsequence("ollow", "llo") andlongest-common-subsequence("llow", "ello").

我不明白的部分是当字符串不以相同的字母开头时，为什么我们采用(没有第一个字母的 s1，s2)，(没有第一个字母的 s1，s2)。当它们不匹配时，为什么我们要递归地执行这些步骤？难道只是一套难懂的算法？这背后的原因是什么？

Answer 1

虽然@yash mahajan 已经涵盖了所有内容，但我将提供另一种思考方式。

遍历两个字符串，假设你在字符串 A(长度为 m)的位置 i 和字符串 B(长度为 n)的位置 j。

<强>1。如果两个字符串的当前两个字符相同:

到目前为止最长公共(public)子序列 = 子串 A[0...i-1] 和子串 B[0...j-1] + 1 之间的最长公共(public)子序列。

<强>2。如果两个字符不同:

longest common subsequence = Max(子串A[0...i-1]和串B的最长公共(public)子串,串A和子串B的最长公共(public)子串[0...j-1])

如果您阅读代码，您会有更清晰的思路。

public class Solution {

    public int longestCommonSubsequence(String A, String B) {
        if(A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }

        int m = A.length();
        int n = B.length();
        int[][] commonSubsequenceLength = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(A.charAt(i - 1) == B.charAt(j - 1)) {
                    commonSubsequenceLength[i][j] = commonSubsequenceLength[i - 1][j - 1] + 1;
                } else {
                    commonSubsequenceLength[i][j] = Math.max(commonSubsequenceLength[i][j - 1], commonSubsequenceLength[i - 1][j]);
                }
            }
        }

        return commonSubsequenceLength[m][n];

    }
}