【LeetCode】Longest Common Subsequence最长公共子序列（求出某一解+LCS长度） - Medium

Longest Common Subsequence 
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。 
说明 
最长公共子序列的定义： 
• 最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。 
• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem 
样例 
给出”ABCD” 和 “EDCA”，这个LCS是 “A” (或 D或C)，返回1 
给出 “ABCD” 和 “EACB”，这个LCS是”AC”返回 2

Challenge 
O(n x m) time and memory. 

例如： 
Xi=1,Yj=1时，∵A≠B ∴c(1,1) = max[c(A),c(B)] = 0; 
Xi=2,Yj=1时，∵B=B ∴c(2,1) = c(2-1,1-1)+1=c(1,0)+1= 1; 
Xi=2,Yj=2时，∵B≠D ∴c(2,2) = maxc(AB,B),c(A,BD) = 1; 
Xi=3,Yi=3时，∵C=C ∴c(3,3)=c(3-1,3-1)+1=c(2,2)+1=1+1=2

C++：

//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>    //max()函数
//#include <math.h>

using namespace std;

void LCS(const char* str1, const char* str2, string& str) {
    int size1 = strlen(str1);
    int size2 = strlen(str2);
    const char* s1 = str1 - 1;//从1开始数，方便后面的代码编写(将字符串指针str1指向了 首元素的前面。)，这样第0行/列，LCS（即c[0][j],c[i][0]) 为0。
    const char* s2 = str2 - 1;
    vector<vector<int>> chess(size1 + 1, vector<int>(size2 + 1));
    //因为是从1起数。而第0行/列是外加的（因为字符串与空串的LCS永远为0）;但是总长需要+1
    //chess棋盘：二维数组，行数为size1，列数为size2
    int i, j;
    //for (i = 0; i < size1; i++) {//第0列初始化为0（其实自动初始化的，可以不写）
    //  chess[i][0] = 0;
    //}
    //for (j = 0; j < size2; j++) {//第0行初始化为0
    //  chess[0][j] = 0;
    //}

    for (i = 1; i < size1; i++) { // 一定要从1起！！！
        for (j = 1; j < size2; j++) {
            if (s1[i] == s2[j]) {
                //若两串当前元素相同，则其当前LCS等于左上角LCS（chess[i - 1][j - 1] ）+ 1（此处加的1，即为当前元素(i,j).）
                chess[i][j] = chess[i - 1][j - 1] + 1;
            }
            else {  // if (s1[i] != s2[j])
                //若两串当前元素不同，则其当前LCS一定等于左边、上边的LCS的最大值。（而到了（i,j）处，不是公共元素。跳过。）
                chess[i][j] = max(chess[i - 1][j], chess[i][j - 1]);
            }
        }
    }
    //到此，排表（棋盘）结束。

    i = size1;//将i、j下标落到末尾元素上。
    j = size2;
    while (i != 0 && j != 0)
    {
        if (s1[i] == s2[j]) {   //将相同的子元素压栈。然后指针前移，直到i、j指向0终止(因为任何字符串 与0 求公共子序列，都是0)
            str.push_back(s1[i]);
            i--;
            j--;
        }
        else { //若二者不相等，而最长公共子序列一定是由LCS（chess[i][j-1] or chess[i-1][j]）的较大者得来，故将较大者的指针前移，接着遍历。
            if (chess[i][j - 1] > chess[i - 1][j]) {
                j--;        //将当前列前移到j-1列
            }
            else { // if(chess[i][j - 1] <= chess[i - 1][j])
                i--;
            }
        }
    }
    //求LCS（之一）
    reverse(str.begin(), str.end());

    //求LCS的长度
    int maxLen = 0;
    for(i = 0; i < size1; i++){
        for(j = 0; j < size2; j++){
            maxLen = max(maxLen, chess[i][j]);
        }
    }
    cout << "LCS length: " << maxLen << endl;

}
void printStr(string str) {
    for (int i = 0; i < str.length(); i++) {
        cout << str[i] ;
    }
    cout << endl;
}
int main()
{
    char* s1 = "TCGGATCGACTT";
    char* s2 = "AGCCTACGTA";
    string str;
    LCS(s1, s2, str);
    printStr(str);
    return 0;
}

JAVA：

//①
public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        int n = A.length();
        int m = B.length();
        int f[][] = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if(A.charAt(i - 1) == B.charAt(j - 1))
                    f[i][j] = f[i - 1][j - 1] + 1;
            }
        }
        return f[n][m];
    }
}


//②【拓展版】求满足的一个LCS子串（之一），并求出其长度
import java.util.Stack;

public class Solution {
    public static int longestCommonSubsequence(String A, String B) {
        // state: f[i][j] is the length of the longest lcs
        // ended with A[i - 1] & B[j - 1] in A[0..i-1] & B[0..j-1]
        int m = A.length();
        int n = B.length();
// （由于任何str与空串的LCS都为零：故将第0行/列全部置0！（默认初始化就是0））
// 因此 分别以A、B为行、列拼成的棋盘chess，行数列数均需+1（<-第0行/列）
        int chess[][] = new int[m + 1][n + 1];
        int i, j;
//        Stack<Character> stack = null;
        StringBuffer sb = new StringBuffer();


//      从第1行/列开始数。
        for (i = 1; i <= m; i++) {
            for (j = 1; j <= n; j++) {
//      由于i、j均为1起算，故用i、j表示字符串下标时，需要减1（而棋盘chess不需要考虑这个，因为第0行/列本就算做另加的）
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    chess[i][j] = chess[i - 1][j - 1] + 1;
                } else {
                    chess[i][j] = 0;
                }
            }
        }

        //求最长公共子序列的长度
        int max = 0;
        for ( i = 1; i <= m; i++) {
            for ( j = 1; j <= n; j++) {
                max = Math.max(max, chess[i][j]);
            }
        }
        //棋盘chess中的值已设置完成。

        //将i、j下标落到末尾元素上。（以之为起点，一直走到头）
        i = m;
        j = n;
        //求LCS解（之一）
        try {
            while (i != 0 && j != 0) {//当i、j到达第0行/列时，棋盘走到尽头。
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
//                    System.out.println("i: "+i+", j: "+j+"    "+A.charAt(i - 1)+" ; "+B.charAt(j - 1)); //Debug
                    sb.append(A.charAt(i - 1));//将相同的子元素压栈。然后指针前移，直到i、j指向0终止(因为任何字符串 与0 求公共子序列，都是0)
                    i--;
                    j--;
                } else { //若二者不相等，而最长公共子序列一定是由LCS（chess[i][j-1] or chess[i-1][j]）的较大者得来，故将较大者的指针前移，接着遍历。
                    if (chess[i][j - 1] > chess[i - 1][j]) {
                        j--;
                    } else { //if(chess[i][j-1] <= chess[i-1][j])
                        i--;
                    }

                }
            }
            System.out.println("One of the Longest Common Subsequence: " + sb.reverse());
        }catch (NullPointerException e){
            System.err.println("NullPointerException!");
        }
        return max;
    }
    public static void main(String[] args){
        String A = "TCGGATCGACTT";
        String B = "AGCCTACGTA";
        int num = longestCommonSubsequence(A,B);
        System.out.println("Its length: " + num);
    }
}

原文链接：https://blog.csdn.net/ljyljyok/article/details/77905681