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à các chuỗi con. Có thể có nhiều hơn một kết quả, nên chúng ta sẽ chỉ trả về 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ự từ T (có thể là 0, và các ký tự được chọn ở bất kỳ đâu từ T) cho ra chuỗi S.
Vì vậy, nếu đầu vào giống như "acab", "bac", thì đầu ra sẽ là "bacab", vì hai chuỗi cho trước là chuỗi con của chuỗi này.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa hàm getLCS(), nhận s1, s2,
ret := chuỗi rỗng
n := kích thước của s1, m := kích thước của s2
Định nghĩa mảng 2D dp kích thước (n + 1) x (m + 1)
i := n, j := m
s1 := nối chuỗi rỗng trước s1
s2 := nối chuỗi rỗng trước s2
for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), thực hiện −
for 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] bằng s2[j], thì −
dp[i, j] := 1 + dp[i - 1, j - 1]
Ngược lại
dp[i, j] := max của dp[i - 1, j] và dp[i, j - 1]
khi (i khác 0 và j khác 0), thực hiện −
nếu dp[i, j] bằng dp[i - 1, j], thì −
(giảm i xuống 1)
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
nếu dp[i, j] bằng dp[i, j - 1], thì −
(giảm j xuống 1)
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
ret := ret + s1[i]
(giảm i xuống 1)
(giảm j xuống 1)
đảo ngược mảng ret
trả về ret
Từ phương thức main thực hiện như sau −
s3 := getLCS(str1, str2)
ret := chuỗi rỗng, i := 0, j := 0, k := 0
khi k < kích thước của s3, thực hiện −
nếu i < kích thước của str1 và str1[i] khác s3[k], thì −
ret := ret + str1[i]
(tăng i lên 1)
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
nếu j < kích thước của str2 và str2[j] khác s3[k], thì −
ret := ret + str2[j]
(tăng j lên 1)
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
ret := ret + s3[k]
(tăng i, j, k lên 1)
khi i < kích thước của str1, thực hiện −
ret := ret + str1[i]
(tăng i lên 1)
khi j < kích thước của str2, thực hiện −
ret := ret + str2[j]
(tăng j lên 1)
trả về ret
Hãy xem 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