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

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

在一个字符串中,子序列是通过删除一些字符形成的字符串,这意味着它包含了字符串中的一些字符,可能是全部或者没有,并且所有字符的顺序与原字符串相同。在两个字符串中,我们需要找到最长的不包含重复字符的公共子序列。

示例

输入

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

输出结果

The length of the longest common subsequence is: 8

解释:在上述给定的字符串中,我们有最长的公共子序列“abcadjmrrc”,如果只考虑独特的字符,那么我们可以通过删除两次出现的 ‘a’、’c’ 和 ‘r’ 来得到“abcdjmor”。

输入

string str1 = “abcdedf”
string str2 =  “xayjklf”

Output

The length of the longest common subsequence is: 2

解释:在这里,我们只有两个常见的字符,它们都是’af’。

递归方法

在这种方法中,我们将确定两个给定字符串中共同的所有子序列,并维护唯一字符计数,以防止任何字符重复。

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

我们将在数字中设置当前字符的ASCII值减去字符’a’的ASCII值的位来标记该位。

示例

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

// recursion function 
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));
   }
}
// helper function
int findlen(string str1, string str2){
   int bit = 0; // integer to store the bit values 
   // calling to the recursion function to get the answer 
   int ans = rec(str1, str2, 0, 0, bit);
   return ans; // returning the answer 
}
// main function 
int main(){
   string str1 = "aabcadjmuorrrcc"; // given first string
   string str2 = "adbcwcadjomrorlc"; // given second string 
   // calling the funciton 
   cout<<"The length of the longest common subsequence is: "<<findlen(str1,str2)<<endl;
}

输出

The length of the longest common subsequence is: 8

时间和空间复杂度

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

上述代码的空间复杂度为O(N),这是由于递归堆栈造成的。

记忆化方法

在之前的方法中,对函数的调用次数很多,确切地说是指数级的调用,这使得方法变得低效。因此,我们将使用记忆化方法来存储已经计算过的调用结果。

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

我们将按照之前的代码进行,只需添加一些新的记忆化技巧的代码,即定义和初始化映射。然后将结果存储在映射中,并检查映射中是否已经存在该键。

示例

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

// map for memoization 
map<string, int> memo;
// recursion function 
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];
}
// helper function
int findlen(string str1, string str2){
   int bit = 0; // integer to store the bit values 
   memo = {}; // initializing the map
   // calling to the recursion function to get the answer 
   int ans = rec(str1, str2, 0, 0, bit);
   return ans; // returning the answer 
}
// main function 
int main(){
   string str1 = "aabcadjmuorrrcc"; // given first string
   string str2 = "adbcwcadjomrorlc"; // given second string 
   // calling the function 
   cout<<"The length of the longest common subsequence is: "<<findlen(str1,str2)<<endl;
}

输出结果

The length of the longest common subsequence is: 8

时间和空间复杂度

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

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

结论

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

Camera课程

Python教程

Java教程

Web教程

数据库教程

图形图像教程

办公软件教程

Linux教程

计算机教程

大数据教程

开发工具教程