C++ এ প্যালিনড্রোম পার্টিশনিং

ধরুন আমাদের একটি ইনপুট স্ট্রিং আছে, সেই স্ট্রিংটির একটি পার্টিশনিং হল প্যালিনড্রোম পার্টিশনিং, যখন পার্টিশনের প্রতিটি সাবস্ট্রিং একটি প্যালিনড্রোম। এই বিভাগে, প্রদত্ত স্ট্রিংটিকে প্যালিনড্রোম পার্টিশন করার জন্য আমাদের ন্যূনতম কাটগুলি খুঁজে বের করতে হবে। তাই যদি স্ট্রিংটি "abbbbabbababa" এর মতো হয় তবে প্যালিনড্রোম হিসাবে পার্টিশনে ন্যূনতম কাট। এখানে 3টি কাট প্রয়োজন। প্যালিনড্রোমগুলি হল:a | babbbab | খ | আব্বা

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=str এর দৈর্ঘ্য
কাট ম্যাট্রিক্স এবং পাল ম্যাট্রিক্সের প্রতিটি ক্রম n x n সংজ্ঞায়িত করুন
এর জন্য i :=0 থেকে n, do
- pal[i, i] :=true এবং cut[i, i] :=0
2 থেকে n রেঞ্জের লেনের জন্য, করুন
- আমি 0 থেকে n – লেন রেঞ্জের জন্য, কর
  - j :=i + len – 1
  - যদি len =2, তাহলে
  - যদি str[i] =str[j] হয়, তাহলে pal[i, j] :=সত্য
  - অন্যথায় যখন str[i] =str[j] এবং pal[i+1, j-1] ≠ 0 pal[i, j] :=সত্য
  - যদি pal[i, j] সত্য হয়, তাহলে কাট[i, j] :=0
  - অন্যথায়
    - কাট[i, j] :=∞
    - করুন
      - কাট[i, j] :=ন্যূনতম কাট[i, j] এবং (cut[i, k]+ cut[k+1, j+1]+1)
রিটার্ন কাট[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