leetcode1143：最长公共子序列

题目链接

leetcode

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下，删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    状态表示：
        f[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度，取 max。
    状态计算：
        a[i] != b[j]: 
            f[i][j] = max(f[i - 1][j], f[i][j - 1])
        a[i] == b[j]: 
            f[i][j] = f[i - 1][j - 1] + 1
    初始化：
        f[0][j] = 0，其中 i = 0, 0 <= j <= n        
        f[i][0] = 0，其中 j = 0, 0 <= i <= n

    时间复杂度：O(mn)
        其中 m 和 n 分别是两个字符串的长度。
    空间复杂度：O(mn)
*/
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        if (m == 0 || n == 0) return 0;

        // text1 = ' ' + text1, text2 = ' ' + text2;
        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        // base case
        for (int i = 0; i <= m; i ++) f[i][0] = 0;
        for (int j = 0; j <= n; j ++) f[0][j] = 0;

        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (text1[i - 1] == text2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }

        return f[m][n];
    }
};

/*
    思路同上，优化空间

    时间复杂度：O(mn)
        其中 m 和 n 分别是两个字符串的长度。
    空间复杂度：O(n)
*/
class Solution_1 {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        if (m == 0 || n == 0) return 0;

        vector<int> f(n + 1, 0);
        for (int i = 1; i <= m; i ++) {
            int prev = f[0]; // 存储上一行的第一个元素
            for (int j = 1; j <= n; j ++) {
                int temp = f[j];
                if (text1[i - 1] == text2[j - 1]) {
                    f[j] = prev + 1;  // 当前字符匹配，长度加1
                } else {
                    f[j] = max(f[j], f[j - 1]); // 当前字符不匹配，取另一行的最大值
                }
                prev = temp;
            }
        }

        return f[n];
    }
};

int main() {
    Solution solution;
    vector<string> text1_cases = {"abcde", "ace", "abc"};
    vector<string> text2_cases = {"ace", "abc", "def"};

    for (int i = 0; i < text1_cases.size(); i ++) {
        string text1 = text1_cases[i];
        string text2 = text2_cases[i];
        cout << "text1 = " << text1 << ", text2 = " << text2 << endl;
        int result = solution.longestCommonSubsequence(text1, text2);
        cout << "The length of the longest common subsequence is: " << result << endl;
    }
    
    return 0;
}

Golang 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package main

import (
	"fmt"
)

/*
   动态规划：
       使用二维数组 dp，其中 dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度。
       初始化 dp[0][j] 和 dp[i][0] 为 0，因为空字符串的最长公共子序列长度为 0。
       遍历两个字符串，如果当前字符相等，则 dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
   边界条件：
       如果任意一个字符串为空，返回 0。

   时间复杂度：O(mn)
       遍历两个字符串的每个字符，时间复杂度为 O(mn)，其中 m 和 n 分别是两个字符串的长度。
   空间复杂度：O(mn)
       使用了一个大小为 (m+1)*(n+1) 的二维数组 dp，空间复杂度为 O(mn)。
*/
// longestCommonSubsequence 返回两个字符串的最长公共子序列的长度
func longestCommonSubsequence(text1, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m + 1)
	for i := range dp {
		dp[i] = make([]int, n + 1)
	}

	// 动态规划填表
	for i := 1; i <= m; i ++ {
		for j := 1; j <= n; 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])
			}
		}
	}

	return dp[m][n]
}

/*
    思路同上，优化空间

    时间复杂度：O(mn)
    空间复杂度：O(n)
*/
// longestCommonSubsequence 返回两个字符串的最长公共子序列的长度
func longestCommonSubsequence_1(text1, text2 string) int {
	m, n := len(text1), len(text2)
	if m < n {
		// 交换 text1 和 text2，确保 text1 是较短的那个
		text1, text2 = text2, text1
		m, n = n, m
	}

	// 使用一维数组存储当前行和上一行的状态
	prev := make([]int, n + 1)
	curr := make([]int, n + 1)

	// 动态规划填表
	for i := 1; i <= m; i ++ {
		for j := 1; j <= n; j ++ {
			if text1[i-1] == text2[j-1] {
				curr[j] = prev[j-1] + 1
			} else {
				curr[j] = max(prev[j], curr[j-1])
			}
		}
		// 交换当前行和上一行
		prev, curr = curr, prev
	}

	return prev[n]
}

func main() {
	// 测试用例
	testCases := []struct {
		text1    string
		text2    string
		expected int
	}{
		{
			text1:    "abcde",
			text2:    "ace",
			expected: 3,
		},
		{
			text1:    "abc",
			text2:    "abc",
			expected: 3,
		},
		{
			text1:    "abc",
			text2:    "def",
			expected: 0,
		},
	}

	for i, tc := range testCases {
		result := longestCommonSubsequence(tc.text1, tc.text2)
		fmt.Printf("Test Case %d, Input: text1 = %q, text2 = %q\n", i+1, tc.text1, tc.text2)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}
#leetcode
leetcode1143：最长公共子序列
https://lcf163.github.io/2024/05/26/leetcode1143：最长公共子序列/
作者
乘风的小站
发布于
2024年5月26日
许可协议