ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের এই স্ট্রিংটিকে বিভিন্ন সাবস্ট্রিংয়ে ভাগ করার জন্য প্রয়োজনীয় কাটগুলির সংখ্যা খুঁজে বের করতে হবে এবং প্রতিটি অংশ একটি প্যালিনড্রোম। সুতরাং যদি স্ট্রিংটি "আবাব্বা" এর মত হয়, তাহলে এটি 2টি কাট নেবে। [aba|bb|a]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=স্ট্রিং s
-এ অক্ষরের সংখ্যা -
n + 1
আকারের res নামক একটি অ্যারে তৈরি করুন -
res[n] :=-1
-
i রেঞ্জ n – 1 থেকে 0
পর্যন্ত-
res[i] :=n – i – 1
-
j এর জন্য i থেকে n
পরিসরে-
যদি a এর সাবস্ট্রিং, সূচক i থেকে j - i একটি প্যালিনড্রোম হয়, তাহলে
-
res[i] :=ress[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
