最长公共子序列（LCS）的python、C、C++、Java实现 LeetCode72、LeetCode1143_python lcs

     

目录

一、原理分析

二、代码实现

        1、Python 实现

        2、C语言实现

        3、C++实现

       4、JAVA实现

三、例题解析

        1、LeetCode1143.最长公共子序列

        2、LeetCode72.编辑距离

---

       最长公共子序列（Longest Common Subsequence，LCS）是一种常见的计算机科学问题，涉及到在两个序列（通常是字符串）中找到最长的子序列，这个子序列是这两个序列共有的。本文将深入探讨LCS的原理、不同编程语言的实现方法，并通过解析Leetcode中的例题来展示其实际应用。

一、原理分析

        最长公共子序列问题可以通过动态规划来解决。

        动态规划是一种将复杂问题分解为更小的子问题，并将这些子问题的解决方案存储在表格中以便重复使用的技术。

        在LCS问题中，我们可以创建一个二维表格，其中每个单元格代表两个输入字符串的一个子字符串，并存储这两个子字符串的最长公共子序列的长度。

为了填充这个表格，我们可以使用以下规则：

1. 如果两个子字符串的最后一个字符相同，那么他们的LCS长度就是去掉这两个字符后的子字符串的LCS长度加1。
2. 如果两个子字符串的最后一个字符不同，那么他们的LCS长度就是去掉一个字符串的最后一个字符后的子字符串的LCS长度和去掉另一个字符串的最后一个字符后的子字符串的LCS长度中的最大值。

       通过从输入字符串的末尾开始应用这些规则，并递归地解决更小的子问题，我们可以填充整个表格，并最终找到最长公共子序列的长度。

二、代码实现

        1、Python 实现

def lcs(X, Y):  
    m = len(X)  
    n = len(Y)  
    L = [[0 for j in range(n+1)] for i in range(m+1)]  
    for i in range(m+1):  
        for j in range(n+1):  
            if i == 0 or j == 0:  
                L[i][j] = 0  
            elif X[i-1] == Y[j-1]:  
                L[i][j] = L[i-1][j-1] + 1  
            else:  
                L[i][j] = max(L[i-1][j], L[i][j-1])  
    return L[m][n]

        2、C语言实现

#include <stdio.h>  
#include <stdlib.h>  
int max(int a, int b) { return (a > b)? a : b; }  
int lcs(char *X, char *Y, int m, int n) {  
    int L[m+1][n+1];  
    int i, j;  
    for (i = 0; i <= m; i++) {  
        for (j = 0; j <= n; j++) {  
            if (i == 0 || j == 0) {  
                L[i][j] = 0;  
            } else if (X[i-1] == Y[j-1]) {  
                L[i][j] = L[i-1][j-1] + 1;  
            } else {  
                L[i][j] = max(L[i-1][j], L[i][j-1]);  
            }  
        }  
    }  
    return L[m][n];  
}

        3、C++实现

#include <iostream>  
#include <vector>  
#include <algorithm>  
using namespace std;  
int lcs(string X, string Y) {  
    int m = X.size();  
    int n = Y.size();  
    vector<vector<int>> L(m+1, vector<int>(n+1, 0));  
    for (int i = 1; i <= m; i++) {  
        for (int j = 1; j <= n; j++) {  
            if (X[i-1] == Y[j-1]) {  
                L[i][j] = L[i-1][j-1] + 1;  
            } else {  
                L[i][j] = max(L[i-1][j], L[i][j-1]);  
            }  
        }  
    }  
    return L[m][n];  
}  

       4、JAVA实现

public class LCS {  
    public static int lcs(String X, String Y) {  
        int m = X.length();  
        int n = Y.length();  
        int[][] L = new int[m+1][n+1];  
        for (int i = 0; i <= m; i++) {  
            for (int j = 0; j <= n; j++) {  
                if (i == 0 || j == 0) {  
                    L[i][j] = 0;  
                } else if (X.charAt(i-1) == Y.charAt(j-1)) {  
                    L[i][j] = L[i-1][j-1] + 1;  
                } else {  
                    L[i][j] = Math.max(L[i-1][j], L[i][j-1]);  
                }  
            }  
        }  
        return L[m][n];  
    }  
}

三、例题解析

        1、LeetCode1143.最长公共子序列

            （1）题目链接：https://leetcode.com/problems/longest-common-subsequence/

            （2）题意解析：给定两个字符串text1和text2，找出它们的最长公共子序列的长度。一个字符串的最长公共子序列是指这个字符串与另一个字符串的最长公共子序列。

            （3）解题思路：给定两个字符串text1和text2，找出它们的最长公共子序列的长度。一个字符串的最长公共子序列是指这个字符串与另一个字符串的最长公共子序列。

            （4）AC代码：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
      X = text1
      Y = text2
      m = len(X)  
      n = len(Y)  
      L = [[0 for j in range(n+1)] for i in range(m+1)]  
      for i in range(m+1):  
          for j in range(n+1):  
              if i == 0 or j == 0:  
                  L[i][j] = 0  
              elif X[i-1] == Y[j-1]:  
                  L[i][j] = L[i-1][j-1] + 1  
              else:  
                  L[i][j] = max(L[i-1][j], L[i][j-1])  
      return L[m][n]

        2、LeetCode72.编辑距离

          （1）题目链接：https://leetcode.cn/problems/edit-distance

          （2）题意解析：给定两个单词word1和word2，计算将word1转换为word2所需的最小编辑距离。编辑距离是指将一个单词转换为另一个单词所需的最少单字符编辑（插入、删除或替换）次数。

          （3）解题思路：使用二维数组dp，其中dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小编辑距离。如果word1[i-1]等于word2[j-1]，则dp[i][j]等于dp[i-1][j-1]；否则，dp[i][j]等于dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]中的最小值加1。

          （4）AC代码：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        X = word1
        Y = word2
        m = len(X)  
        n = len(Y)  
        L = [[0 for j in range(n+1)] for i in range(m+1)]  
        for i in range(m+1):  
            for j in range(n+1):  
                if i == 0 and j == 0:  
                    L[i][j] = 0
                elif i == 0 and j != 0:
                    L[i][j] = j
                elif i != 0 and j == 0:
                    L[i][j] = i  
                elif X[i-1] == Y[j-1]:  
                    L[i][j] = L[i-1][j-1]  
                else:  
                    L[i][j] = min(L[i-1][j], L[i][j-1], L[i - 1][j - 1]) + 1  
        return L[m][n]