Giả sử chúng ta có hai chuỗi str1 và str2, chúng ta phải tìm chuỗi ngắn nhất có cả str1 và str2 là chuỗi con. Có thể có nhiều hơn một kết quả, vì vậy chúng tôi sẽ chỉ trả lại một trong số chúng.
Như bạn đã biết, một chuỗi S được gọi là chuỗi con của chuỗi T nếu xóa một số ký tự khỏi T (có thể là 0 và các ký tự được chọn ở bất kỳ đâu từ T) sẽ dẫn đến chuỗi S.
Vì vậy, nếu đầu vào giống như "acab", "bac", thì đầu ra sẽ là "bacab", điều này là do hai chuỗi đã cho là chuỗi con của chuỗi này.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm getLCS (), hàm này sẽ lấy s1, s2,
-
ret:=chuỗi trống
-
n:=kích thước của s1, m:=kích thước của s2
-
Xác định một dp mảng 2D có kích thước (n + 1) x (m + 1)
-
i:=n, j:=m
-
s1:=nối chuỗi trống trước s1
-
s2:=nối chuỗi trống trước s2
-
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
-
để khởi tạo j:=1, khi j <=m, cập nhật (tăng j lên 1), thực hiện -
-
nếu s1 [i] giống s2 [j] thì -
-
dp [i, j]:=1 + dp [i - 1, j - 1]
-
-
Nếu không
-
dp [i, j]:=tối đa của dp [i - 1, j] và dp [i, j - 1]
-
-
-
-
while (i là khác 0 và j là khác 0), do -
-
nếu dp [i, j] giống với dp [i - 1, j] thì -
-
(giảm i đi 1)
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
nếu dp [i, j] giống với dp [i, j - 1] thì -
-
(giảm j đi 1)
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
ret:=ret + s1 [i]
-
(giảm i đi 1)
-
(giảm j đi 1)
-
-
đảo ngược mảng ret
-
trả lại ret
-
Từ phương thức chính, thực hiện như sau -
-
s3:=getLCS (str1, str2)
-
ret:=chuỗi trống, i:=0, j:=0, k:=0
-
while k
-
nếu tôi
-
ret:=ret + str1 [i]
-
(tăng tôi lên 1)
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
nếu j
-
ret:=ret + str2 [j]
-
(tăng j lên 1)
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
ret:=ret + s3 [k]
-
(tăng i, j, k lên 1)
-
-
while i
-
ret:=ret + str1 [i]
-
(tăng tôi lên 1)
-
-
while j
-
ret:=ret + str2 [j]
-
(tăng j lên 1)
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2){
string s3 = getLCS(str1, str2);
string ret = "";
int i = 0;
int j = 0;
int k = 0;
while (k < s3.size()) {
if (i < str1.size() && str1[i] != s3[k]) {
ret += str1[i];
i++;
continue;
}
if (j < str2.size() && str2[j] != s3[k]) {
ret += str2[j];
j++;
continue;
}
ret += s3[k];
k++;
i++;
j++;
}
while (i < str1.size()) {
ret += str1[i];
i++;
}
while (j < str2.size()) {
ret += str2[j];
j++;
}
return ret;
}
string getLCS(string s1, string s2){
string ret = "";
int n = s1.size();
int m = s2.size();
vector<vector<int> > dp(n + 1, vector<int>(m + 1));
int i = n;
int j = m;
s1 = " " + s1;
s2 = " " + s2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i] == s2[j]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
while (i && j) {
if (dp[i][j] == dp[i - 1][j]) {
i--;
continue;
}
if (dp[i][j] == dp[i][j - 1]) {
j--;
continue;
}
ret += s1[i];
i--;
j--;
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.shortestCommonSupersequence("acab", "bac"));
} Đầu vào
"acab", "bac"
Đầu ra
bacab