Giả sử chúng ta có một chuỗi s và một số k khác; chúng ta phải kiểm tra xem chuỗi đã cho có phải là K-Palindrome hay không.
Một chuỗi được cho là K-Palindrome nếu nó có thể được chuyển đổi thành palindrome bằng cách xóa tối đa k ký tự khỏi nó.
Vì vậy, nếu đầu vào là s ="abcdeca", k =2, thì kết quả đầu ra sẽ đúng khi loại bỏ các ký tự 'b' và 'e', nó sẽ là palindrome.
Để 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 lcs (), điều này sẽ lấy s, t,
-
n:=kích thước của s
-
thêm một khoảng trống trước s
-
thêm một khoảng trống trước t
-
Xác định một dp mảng 2D có 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), thực hiện -
-
để khởi tạo j:=1, khi j <=n, cập nhật (tăng j lên 1), thực hiện -
-
dp [i, j]:=tối đa của dp [i - 1, j] và dp [i, j - 1]
-
nếu s [i] giống với t [j] thì -
-
dp [i, j]:=tối đa của dp [i, j] và 1 + dp [i - 1, j - 1]
-
-
-
-
trả về dp [n, n]
-
Từ phương thức chính, hãy làm như sau -
-
nếu không phải là kích thước của s, thì -
-
trả về true
-
-
x:=khoảng trống
-
để khởi tạo i:=kích thước của s, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
-
x:=x + s [i]
-
-
kích thước trả về của s
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 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