0024.最长公共子序列.md

24. 最长公共子序列

题目链接

代码随想录算法讲解

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
    string text1, text2;
    while (cin >> text1 >> text2) {
         vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        cout << dp[text1.size()][text2.size()] << endl;
    }
    return 0;
}

Java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            String[] s = line.split(" ");
            String x = s[0];
            String y = s[1];
            int m = x.length();
            int n = y.length();
            //dp[i][j] 意为 字符串x的i-1 字符串y的j-1的位置的最大长度是多少
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (x.charAt(i - 1) == y.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            int max = dp[m][n];
            System.out.println(max);
        }
    }

}

python

while True:
    try:
        text1, text2 = input().split()
    except:
        break
    
    dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
    for i in range(1, len(text1) + 1):
        for j in range(1, len(text2) + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    print(dp[len(text1)][len(text2)])

Go

package main

import (
	"fmt"
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func longestCommonSubsequence(X, Y string) int {
	m := len(X)
	n := len(Y)

	// 创建一个二维数组dp，dp[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if X[i-1] == Y[j-1] {
				// 当X的第i个字符等于Y的第j个字符时，最长公共子序列长度加1
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				// 否则，取不包含X的第i个字符的最长公共子序列长度和不包含Y的第j个字符的最长公共子序列长度的最大值
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}

	return dp[m][n]
}

func main() {
	var X, Y string
	for {
		_, err := fmt.Scan(&X, &Y)
		if err != nil {
			break
		}
		result := longestCommonSubsequence(X, Y)
		fmt.Println(result)
	}
}

Js

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output:process.stdout,
})

rl.on('line',function(line){
    const input = line.split(' ');
    const str1 = input[0], str2 = input[1];
    const len1 = str1.length, len2 = str2.length;
    const dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0));
    for(let i = 1; i <= str1.length; i++) {
        for(let j = 1; j <= str2.length; j++) {
            if(str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else {
                dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1],dp[i][j]);
            }
        }
    }
    console.log(dp[len1][len2]);
})

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    char text1[100];
    char text2[100];
    while (scanf("%s %s", text1, text2) == 2) {
        int dp[101][101] = {0}; // 注意数组大小要根据实际情况选择

        int len1 = strlen(text1);
        int len2 = strlen(text2);

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        printf("%d\n", dp[len1][len2]);
    }
    return 0;
}