สมมติว่าเรามีอินพุตสตริงหนึ่งสตริง การแบ่งพาร์ทิชันของสตริงนั้นเป็นการแบ่งพาร์ทิชันแบบพาลินโดรม เมื่อทุกสตริงย่อยของพาร์ติชั่นเป็นพาลินโดรม ในส่วนนี้ เราต้องค้นหาการตัดขั้นต่ำที่จำเป็นสำหรับ palindrome ที่แบ่งสตริงที่กำหนด ดังนั้นหากสตริงเป็นเหมือน “ababbbabbababa” ให้ตัดขั้นต่ำเป็นพาร์ติชั่นเป็น palindrome ที่นี่จำเป็นต้องตัด 3 ครั้ง palindromes คือ:a | บับเบิ้ล | ข | อาบาบา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ความยาวของ str
- กำหนด cut matrix และ pal matrix ตามลำดับ n x n
- สำหรับ i :=0 ถึง n ทำ
- pal[i, i] :=true และ cut[i, i] :=0
- สำหรับเลนในช่วง 2 ถึง n ทำ
- สำหรับฉันในช่วง 0 ถึง n – len ทำ
- j :=i + len – 1
- ถ้า len =2 แล้ว
- ถ้า str[i] =str[j] แล้ว pal[i, j] :=true
- อย่างอื่นเมื่อ str[i] =str[j] และ pal[i+1, j-1] ≠ 0 pal[i, j] :=true
- ถ้า pal[i, j] เป็นจริง ให้ตัด[i, j] :=0
- อย่างอื่น
- ตัด[i, j] :=∞
- สำหรับ k ในช่วง i ถึง j-1 ทำ
- cut[i, j] :=ขั้นต่ำของ cut[i, j] และ (cut[i, k]+ cut[k+1, j+1]+1)
- สำหรับฉันในช่วง 0 ถึง n – len ทำ
- ตัดกลับ[0, n-1]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −
#include <iostream>
#include <climits>
using namespace std;
int min (int a, int b){
return (a < b)? a : b;
}
int minPalPartion(string str){
int n = str.size();
int cut[n][n];
bool pal[n][n]; //true when palindrome present for i to j th element
for (int i=0; i<n; i++){
pal[i][i] = true; //substring of length 1 is plaindrome
cut[i][i] = 0;
}
for (int len=2; len<=n; len++){
for (int i=0; i<n-len+1; i++){//find all substrings of length len
int j = i+len-1; // Set ending index
if (len == 2) //for two character string
pal[i][j] = (str[i] == str[j]);
else //for string of more than two characters
pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];
if (pal[i][j] == true)
cut[i][j] = 0;
else{
cut[i][j] = INT_MAX; //initially set as infinity
for (int k=i; k<=j-1; k++)
cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j]+1);
}
}
}
return cut[0][n-1];
}
int main(){
string str= "ababbbabbababa";
cout << "Min cuts for Palindrome Partitioning is: "<<minPalPartion(str);
} อินพุต
ababbbabbababa
ผลลัพธ์
Min cuts for Palindrome Partitioning is: 3
