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