C++ 中不含重复字符的最长公共子序列

2024 年 8 月 29 日 | 阅读 6 分钟

最长公共子序列 (LCS) 问题是一个经典的动态规划问题，旨在找出两个给定序列的共同最长子序列的长度。

算法

初始化一个二维数组（矩阵）

创建一个维度为 (m + 1) x (n + 1) 的二维数组 dp，其中 m 和 n 是两个输入字符串的长度。

填充矩阵

使用两个嵌套循环遍历两个字符串的字符。循环索引为 i 和 j，范围从 0 到 m 和 0 到 n。

检查字符相等性和无重复条件

在矩阵的每个 位置 (i, j)，检查字符 s1[i-1] 和 s2[j-1] 是否相等且在各自子字符串中不重复。

如果它们相等且不重复，则将 dp[i][j] 设置为 dp[i-1][j-1] + 1。

如果它们不相等，则将 dp[i][j] 设置为 dp[i-1][j] 和 dp[i][j-1] 中的最大值。

最终结果

右下角单元格 dp[m][n] 将包含无重复字符的 LCS 长度。

程序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestCommonSubsequenceNoRepeatingChar(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    // Create a 2D array to store the length of the LCS for each pair of substrings
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    // Fill the dp table using bottom-up dynamic programming
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // If the characters are equal and non-repeating, then add 1 to the LCS length
            if (s1[i - 1] == s2[j - 1] && count(s1.begin(), s1.begin() + i - 1, s1[i - 1]) == 0 &&
                count(s2.begin(), s2.begin() + j - 1, s2[j - 1]) == 0) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // If characters are not equal, take the maximum of the previous LCS lengths
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // The result is stored in the bottom-right cell of the dp table
    return dp[m][n];
}
int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCAB";
    int result = longestCommonSubsequenceNoRepeatingChar(s1, s2);
    cout << "Length of the longest common subsequence with no repeating characters: " << result << endl;
    return 0;
}

输出

Length of the longest common subsequence with no repeating characters: 2

复杂度分析

时间复杂度

该算法的时间复杂度为 O(m * n)，其中 'm' 和 'n' 是输入字符串 s1 和 s2 的长度。这是因为有一个嵌套循环遍历两个字符串的每个字符，并且循环内部执行的工作是常数时间。

空间复杂度

空间复杂度也为 O(m * n)。这是由于用于存储每对子字符串的 LCS 长度的维度为 (m + 1) x (n + 1) 的二维向量 dp。空间复杂度与此矩阵的大小成正比。

在最坏情况下，整个矩阵需要被填充，导致 O(m * n) 的空间复杂度。

方法 1：使用带有记忆化的递归方法

带有记忆化的递归方法 涉及将问题分解为更小的子问题，并缓存这些子问题结果以避免冗余计算。

程序

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Function to calculate LCS length with no repeating characters using recursion and memorization
int lcsRecursiveWithMemo(string &s1, string &s2, int i, int j, unordered_map<string, int> &memo) {
    // Base case: when either of the indices reaches 0, the LCS length is 0
    if (i == 0 || j == 0) {
        return 0;
    }
    // Create a unique key for the memoization table
    string key = to_string(i) + "_" + to_string(j);
    // Check if the result for the current subproblem is already memoized
    if (memo.find(key) != memo.end()) {
        return memo[key];
    }
    // Check if the characters are equal
    bool charactersEqual = (s1[i - 1] == s2[j - 1]);
    // Check for non-repeating characters in both substrings
    for (int k = i - 1; k >= 0; --k) {
        if (s1[k] == s1[i - 1]) {
            charactersEqual = false;
            break;
        }
    }
    for (int k = j - 1; k >= 0; --k) {
        if (s2[k] == s2[j - 1]) {
            charactersEqual = false;
            break;
        }
    }
    // If characters are equal and non-repeating, recursively calculate LCS
    if (charactersEqual) {
        memo[key] = 1 + lcsRecursiveWithMemo(s1, s2, i - 1, j - 1, memo);
    } else {
        // If characters are not equal, take the maximum of the previous LCS lengths
        memo[key] = max(lcsRecursiveWithMemo(s1, s2, i - 1, j, memo), lcsRecursiveWithMemo(s1, s2, i, j - 1, memo));
    }
    return memo[key];
}
// Main function to initiate LCS calculation with memoization
int longestCommonSubsequenceNoRepeatingCharRecursive(string &s1, string &s2) {
    int m = s1.length();
    int n = s2.length();
    unordered_map<string, int> memo;
    return lcsRecursiveWithMemo(s1, s2, m, n, memo);
}
int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCAB";
    int result = longestCommonSubsequenceNoRepeatingCharRecursive(s1, s2);
    cout << "Length of the longest common subsequence with no repeating characters: " << result << endl;
    return 0;
}

输出

Length of the longest common subsequence with no repeating characters: 0

说明

递归函数

主函数是 lcsRecursiveWithMemo，它使用递归方法计算不含重复字符的 LCS 长度。

基本情况

该函数有一个停止递归的基例

当任何一个索引 （i 或 j） 达到 0 时，表示其中一个输入字符串的末尾。在这种情况下，LCS 长度被认为是 0。

记忆化

记忆化用于优化递归解决方案。它涉及存储和重用先前计算的结果，以避免冗余计算。

一个记忆化表 (unordered_map) 用于根据当前索引 i 和 j 的组合存储结果。

非重复字符检查

原始代码使用 count 函数检查非重复字符。但是，由于编译错误，实施了使用显式循环的替代方法。

该函数检查 LCS 中当前正在考虑的字符是否在各自的子字符串中不重复。如果它重复，则 LCS 不能有重复字符。

递归逻辑

如果当前位置的字符相等且不重复，则该函数递归地计算前一个位置 (i-1, j-1) 的 LCS 长度 并加 1。

如果字符不相等，则它取通过排除 s1 的最后一个字符或 s2 的最后一个字符获得的 LCS 长度的最大值。

结果

通过使用输入字符串的长度作为初始索引调用递归函数，获得最终结果。结果表示不含重复字符的最长公共子序列的长度。

主函数

longestCommonSubsequenceNoRepeatingCharRecursive 函数作为入口点，初始化记忆化表并调用递归函数。

示例用法

主函数中的示例演示了对字符串 “ABCBDAB” 和 “BDCAB” 的用法。之后，结果打印到控制台。

复杂度分析

时间复杂度

该算法的时间复杂度为 O(m * n)，其中 'm' 和 'n' 是输入字符串 s1 和 s2 的长度。

通过记忆化，该函数通过存储和重用已解决子问题的结果来避免冗余计算。这显著减少了递归调用的数量，使时间复杂度比朴素递归方法更高效。

空间复杂度

由于记忆化表的存在，空间复杂度为 O(m * n)。该表在递归调用期间存储索引 (i, j) 的所有唯一组合的结果。在最坏情况下，整个表需要被填充，导致 O(m * n) 的空间复杂度。

除了记忆化表之外，空间复杂度还包括递归调用堆栈，其最大深度可以达到递归树的最大深度。在最坏情况下，它将是 O(m + n)。

下一主题C++ 中达到给定 MEX 的最小增量

C++ 中不含重复字符的最长公共子序列

算法

程序

方法 1：使用带有记忆化的递归方法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中不含重复字符的最长公共子序列

算法

程序

方法 1：使用带有记忆化的递归方法

程序

相关帖子

C++ DDA 画线算法

C++ 用户定义大小的二维向量

C++ 不使用第三方变量交换两个数字的程序

C++ Override 关键字

C++ 程序使用 DFS 查找岛屿数量

C++ 中的 match_results prefix() 和 suffix()

C++ 大整数 (Big Integers) 及示例

C++ munmap_chunk 无效指针

C++ Static Cast

C++ ratio_less_equal() 函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器