मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें इस स्ट्रिंग को विभिन्न उपस्ट्रिंग में विभाजित करने के लिए आवश्यक कट की संख्या ढूंढनी है और प्रत्येक भाग एक पालिंड्रोम है। तो यदि स्ट्रिंग "ababba" जैसी है, तो इसमें 2 कट लगेंगे। [aba|bb|a]
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
n := स्ट्रिंग s में अक्षरों की संख्या
आकार n + 1 की एक सरणी res बनाएं
res[n] := -1
i को n - 1 से 0 तक नीचे की ओर
res[i] := n - i - 1
j को i से n तक की रेंज में
यदि इंडेक्स i से, j - i लंबाई का a का उपस्ट्रिंग एक पालिंड्रोम है, तो
res[i] := res[i] और 1 + res[j + 1] का न्यूनतम
res[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
