資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學無重複字元的最長公共子序列
在一個字串中，子序列是可以透過刪除其中一些字元形成的字串，這意味著它包含字串中的一些字元，可能是全部或部分，並且所有字元都將以與字串相同的順序出現。在兩個字串中，我們必須找到最長的公共子序列，該子序列不包含任何重複的字元。
示例
輸入
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”
輸出
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)，空間複雜度也相同。
瀏覽量：173
