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),空间复杂度也相同。