สมมติว่าเรามีสตริง s และอีกตัวเลข k เราต้องตรวจสอบว่าสตริงที่ให้มาเป็น K-Palindrome หรือไม่
สตริงถูกกล่าวว่าเป็น K-Palindrome หากมันสามารถแปลงเป็นพาลินโดรมได้โดยการลบตัวอักษรสูงสุด k ตัวจากมัน
ดังนั้น หากอินพุทคือ s = "abcdeca", k = 2 ผลลัพธ์จะเป็น true เนื่องจากลบ 'b' และ 'e' แล้วจะกลายเป็นพาลินโดรม
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
กำหนดฟังก์ชัน lcs() รับ s, t
n := ขนาดของ s
เพิ่มช่องว่างหน้าสตริง s และ t
กำหนดอาเรย์ 2 มิติ dp ขนาด (n+1) x (n+1)
for i := 1 ถึง n, for j := 1 ถึง n:
dp[i][j] := max(dp[i-1][j], dp[i][j-1])
ถ้า s[i] == t[j]: dp[i][j] := max(dp[i][j], 1 + dp[i-1][j-1])
คืนค่า dp[n][n]
จาก main method:
ถ้า s ว่าง: คืนค่า true
x := สตริงว่าง
for i := ขนาดของ s - 1 ถึง 0: x := x + s[i]
คืนค่า (ขนาดของ s - lcs(s, x) ≤ k)
ตัวอย่างโค้ด
#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> dp(n + 1, vector(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;
}
};
int main() {
Solution ob;
cout << (ob.isValidPalindrome("abcdeca", 2));
return 0;
}
อินพุต
"abcdeca", 2
เอาต์พุต
1
