ধরুন আমাদের একটি ছোট হাতের স্ট্রিং s আছে, আমাদের এটিকে যতটা সম্ভব কয়েকটি স্ট্রিংয়ে বিভক্ত করতে হবে যাতে প্রতিটি স্ট্রিং একটি প্যালিনড্রোম হয় এবং তারপরে স্ট্রিংগুলির সংখ্যা খুঁজে বের করতে হবে৷
সুতরাং, যদি ইনপুটটি s ="লেভেলরেকার" এর মত হয়, তাহলে আউটপুট হবে 2, কারণ দুটি প্যালিনড্রোম "লেভেল" এবং "রেসকার" আছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=A
এর আকার -
আকারের একটি অ্যারের ফলাফল নির্ধারণ করুন (n + 1)
-
ফলাফল[n] :=-1
-
আরম্ভ করার জন্য i :=n - 1, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), করুন −
-
ফলাফল[i] :=n - i - 1
-
j শুরু করার জন্য :=i, যখন j
-
যদি A এর সাবস্ট্রিং i থেকে j পর্যন্ত - i হয় প্যালিনড্রোম, তাহলে −
-
ফলাফল[i] :=সর্বনিম্ন ফলাফল[i] এবং 1 + ফলাফল[j + 1]
-
-
-
-
ফেরত ফলাফল[0] + 1
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
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] + 1;
}
};
int solve(string s) {
return (new Solution())->solve(s);
}
int main(){
string s = "levelracecar";
cout << solve(s);
} ইনপুট
"levelracecar"
আউটপুট
2
