Giả sử chúng ta có hai chuỗi text1 và text2, chúng ta phải tìm độ dài của dãy con dài nhất của chúng. Như chúng ta biết một chuỗi con của một chuỗi là một chuỗi mới được tạo ra từ chuỗi ban đầu với một số ký tự bị xóa mà không thay đổi thứ tự tương đối của các ký tự còn lại. (Ví dụ:"abe" là một dãy con của "abcde" nhưng "adc" thì không). Dãy con chung của hai chuỗi là dãy con chung cho cả hai chuỗi. Vì vậy, không có dãy con chung nào, hãy trả về 0. Nếu đầu vào giống như “abcde” và “ace”, thì kết quả sẽ là 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của s, m:=kích thước của x
-
nếu n là 0 hoặc m là 0 thì trả về 0
-
s:=chuỗi rỗng, được nối với s
-
x:=chuỗi rỗng, được nối với x
-
ret:=0
-
xác định ma trận dp bậc (n + 1) x (m + 1)
-
cho tôi trong phạm vi từ 1 đến n
-
đối với j trong phạm vi từ 1 đến m
-
dp [i, j]:=max của dp [i, j - 1] và dp [i - 1, j]
-
nếu s [i] =x [j] thì
-
dp [i, j]:=max của dp [i, j], 1 + dp [i - 1, j - 1]
-
-
-
-
trả về dp [n, m]
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:
int longestCommonSubsequence(string s, string x) {
int n = s.size();
int m = x.size();
if(!n || !m) return 0;
s = " " + s;
x = " " + x;
int ret = 0;
vector < vector <int> > dp(n + 1, vector <int>(m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m ; j++){
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(s[i] == x[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.longestCommonSubsequence("abcde", "ace"));
} Đầu vào
"abcde" "ace"
Đầu ra
3