सी ++ में स्ट्रिंग के विभाजन की न्यूनतम संख्या के बाद पैलिंड्रोम की संख्या गिनने का कार्यक्रम

मान लीजिए कि हमारे पास एक लोअरकेस स्ट्रिंग है, हमें इसे यथासंभव कुछ स्ट्रिंग्स में विभाजित करना होगा जैसे कि प्रत्येक स्ट्रिंग एक पैलिंड्रोम हो और फिर स्ट्रिंग्स की संख्या ज्ञात करें।

इसलिए, यदि इनपुट s ="लेवलरेसकार" जैसा है, तो आउटपुट 2 होगा, क्योंकि दो पैलिंड्रोम "लेवल" और "रेसकार" हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=A का आकार
आकार का एक सरणी परिणाम परिभाषित करें (n + 1)
परिणाम [एन] :=-1
इनिशियलाइज़ करने के लिए i :=n-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें
- परिणाम [i] :=n - i - 1
- इनिशियलाइज़ j :=i के लिए, जब j
  - यदि श्रेणी i से j - i तक A का स्थानापन्न पैलिंड्रोम है, तो -
    - परिणाम [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"