สมมติว่าเรามีสตริง s เราต้องหาจำนวนการตัดที่จำเป็นในการแบ่งสตริงนี้ออกเป็นสตริงย่อยที่แตกต่างกัน และแต่ละส่วนจะเป็นพาลินโดรม ดังนั้นถ้าสตริงเป็นเหมือน "aabba" ให้ตัด 2 ครั้ง [aba|bb|a]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=จำนวนอักขระในสตริง s
-
สร้างหนึ่งอาร์เรย์ที่เรียกว่า res ขนาด n + 1
-
res[n] :=-1
-
สำหรับฉันอยู่ในช่วง n – 1 ลงไปที่ 0
-
res[i] :=n – i – 1
-
สำหรับ j ในช่วง i ถึง n
-
ถ้าสตริงย่อยของ a จากดัชนี i ถึง j – i เป็นพาลินโดรม ดังนั้น
-
res[i] :=นาทีของ res[i] และ 1 + res[j + 1]
-
-
-
-
ผลตอบแทน[0]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string A) {
int left = 0;
int right = A.size()-1;
while(left < right) {
if(A[left] != A[right]) {
return 0;
}
left++;
right--;
}
return 1;
}
int solve(string A) {
int n = A.size();
vector<int>result(n+1);
result[n] = -1;
for(int i=n-1;i>=0;i--) {
result[i] = n-i-1;
for(int j=i;j<n;j++) {
if(isPalindrome(A.substr(i, j-i+1))) {
result[i] = min(result[i], 1 + result[j+1]);
}
}
}
return result[0];
}
class Solution {
public:
int minCut(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.minCut("ababba"));
} อินพุต
“ababba”
ผลลัพธ์
2
