Giả sử chúng ta có một chuỗi s và một số k; chúng ta phải kiểm tra xem chuỗi cho trước có phải là K-Palindrome hay không.
Một chuỗi được gọi là K-Palindrome nếu nó có thể biến đổi thành palindrome bằng cách xóa tối đa k ký tự từ nó.
Vì vậy, nếu đầu vào là s = "abcdeca", k = 2, đầu ra sẽ là true vì bằng cách xóa 'b' và 'e', nó sẽ thành palindrome.
Để giải quyết, chúng ta sẽ làm theo các bước:
Định nghĩa hàm lcs(), nhận s, t,
n := kích thước s
Thêm một khoảng trắng trước s
Thêm một khoảng trắng trước t
Định nghĩa mảng 2D dp kích thước (n + 1) x (n + 1)
Khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), làm:
Khởi tạo j := 1, khi j <= n, cập nhật (tăng j lên 1), làm:
dp[i, j] := lớn nhất của dp[i - 1, j] và dp[i, j - 1]
nếu s[i] giống t[j], thì:
dp[i, j] := lớn nhất của dp[i, j] và 1 + dp[i - 1, j - 1]
Trả về dp[n, n]
Từ phương thức main làm sau:
nếu không kích thước s, thì:
Trả về true
x := khoảng trắng
Khởi tạo i := kích thước s, khi i >= 0, cập nhật (giảm i xuống 1), làm:
x := x + s[i]
Trả về kích thước s
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int lcs(string s, string t){ int n = s.size(); s = " " + s; t = " " + t; vector<vector<int> > dp(n + 1, vector<int>(n + 1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); if (s[i] == t[j]) dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]); } } return dp[n][n]; } bool isValidPalindrome(string s, int k) { if (!s.size()) return true; string x = ""; for (int i = s.size() - 1; i >= 0; i--) x += s[i]; return s.size() - lcs(s, x) <= k; } }; main(){ Solution ob; cout << (ob.isValidPalindrome("abcdeca", 2)); }Đầu vào
"abcdeca", 2
Đầu ra
1