HTML CSS JAVASCRIPT PYTHON PYTHON2 JAVA C C++ C# SQL Excel Linux AI PHP 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

无重复字符的最长公共子序列

data structurec++programming

在字符串中，子序列是指可以通过从字符串中删除某些字符而形成的字符串，这意味着它包含字符串中的某些字符，这些字符可能全部存在，也可能全部不存在，并且所有字符的顺序与字符串中的顺序相同。我们需要在两个字符串中找到不包含任何重复字符的最长公共子序列。

示例

输入

string str1 = "aabcadjmuorrrcc"
string str2 = "adbcwcadjomrorlc"

输出

最长公​​共子序列的长度为:8

解释:在上述字符串中，最长公共子序列为"abcadjmrrc"。如果我们只考虑唯一字符，则通过删除出现两次的"a"、"c"和"r"，我们将得到"abcdjmor"。

输入

string str1 = "abcdedf"
string str2 = "xayjklf"

输出

最长公​​共子序列的长度为:2

解释:这里，我们只有两个公共字符，并且都是"af"。

递归方法

在这种方法中，我们将确定两个给定字符串中所有公共子序列，并维护唯一字符数，以确保所有字符都不会重复。

我们将创建一个递归函数，该函数将两个字符串以及指向两个字符串当前索引的指针作为参数。此外，我们将传递一个整数，该整数将使用位掩码的概念存储当前公共子序列中已存在的字符。

我们将标记该位，以设置当前字符的 ASCII 值减去字符"a"的 ASCII 值的位，并将其存储在数字中。

示例

#include <bits/stdc++.h>
using namespace std;

// 递归函数
int rec(string& str1, string& str2, int i, int j, int bit){
   if(i == str1.size() || j == str2.size()){
      return 0;
   }
   if((str1[i] == str2[j])  && (bit & (1 << (str1[i]-'0'))) == 0){
      bit = bit | (i << (str1[i]-'0'));
      return 1 + rec(str1, str2, i+1, j+1, bit);
   } else{ 
      return max(rec(str1,str2,i+1,j,bit), rec(str1,str2,i,j+1,bit));
   }
}
// 辅助函数
int findlen(string str1, string str2){
    int bit = 0; // 用于存储位值的整数
    // 调用递归函数获取答案
    int ans = rec(str1, str2, 0, 0, bit);
    return ans; // 返回答案
}
// 主函数
int main(){
    string str1 = "aabcadjmuorrrcc"; // 给定第一个字符串
    string str2 = "adbcwcadjomrorlc"; // 给定第二个字符串
    // 调用函数
   cout<<"最长公共子序列的长度为: "<<findlen(str1,str2)<<endl;
}

输出

最长公共子序列的长度为: 8

时间和空间复杂度

上述代码的时间复杂度为 O(N*2^N)，其中 N 是两个给定字符串中最大字符串的大小。

上述代码的空间复杂度为 O(N)，这是由于使用了递归堆栈。

记忆化方法

在之前的方法中，函数调用次数很高，更准确地说是指数级调用，导致效率低下。因此，我们将使用记忆化方法来存储已经计算出的调用结果。

我们将使用哈希表以字符串的形式存储键，因为我们使用的是 26 位整数(用于标记唯一字符)，这使得使用数组创建 dp 表变得不可能。

我们将沿用之前的代码，并添加几行新的 memoization 技术，用于定义和初始化 map。然后将结果存储在 map 中，并检查该键是否已存在于 map 中。

示例

#include <bits/stdc++.h>
using namespace std;

// 用于记忆化的映射
map memo;
// 递归函数
int rec(string& str1, string& str2, int i, int j, int bit){
   if(i == str1.size() || j == str2.size()){
      return 0;
   }
   string str = to_string(i) + to_string(j) + to_string(bit);
   if(memo.find(str) != memo.end()){
      return memo[str];
   }
   if((str1[i] == str2[j])  && (bit & (1 << (str1[i]-'0'))) == 0){
      bit = bit | (i << (str1[i]-'0'));
      memo[str] = 1 + rec(str1, str2, i+1, j+1, bit);
   } else{ 
      memo[str] = max(rec(str1,str2,i+1,j,bit), rec(str1,str2,i,j+1,bit));
   }
   return memo[str];
}
// 辅助函数
int findlen(string str1, string str2){
    int bit = 0; // 用于存储位值的整数
    memo = {}; // 初始化映射
    // 调用递归函数获取答案
    int ans = rec(str1, str2, 0, 0, bit);
    return ans; // 返回答案
}
// 主函数
int main(){
    string str1 = "aabcadjmuorrrcc"; // 给定第一个字符串
    string str2 = "adbcwcadjomrorlc"; // 给定第二个字符串
    // 调用函数
   cout<<"最长公共子序列的长度为: "<<findlen(str1,str2)<<endl;
}

输出

最长公共子序列的长度为: 8

时间和空间复杂度

上述代码的时间复杂度为 O(N*M)，其中 N 和 M 是给定字符串的大小。

上述代码的空间复杂度为 O(N*M)，因为我们使用哈希表来存储记忆化结果。

结论

在本教程中，我们实现了一个程序，用于在两个给定字符串中找出不包含任何重复字符的最长子序列。首先，我们实现了递归方法，然后使用哈希表存储已计算的调用结果并返回答案。上述代码的时间复杂度为 O(N*M)，空间复杂度也相同。

相关文章

打印 下一节 ❯❮ 上一节