Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में पालिंड्रोम पार्टिशनिंग III (Palindrome Partitioning III)


मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें लोअरकेस अक्षर हैं और एक पूर्णांक k है। हमें कुछ गुणों को बनाए रखना है। ये हैं -

  • पहले, हमें s के कुछ वर्णों को (यदि आवश्यक हो) अन्य लोअरकेस अंग्रेजी अक्षरों में बदलना होगा।
  • फिर स्ट्रिंग s को k उपस्ट्रिंग में विभाजित करना होगा ताकि प्रत्येक उपस्ट्रिंग एक पालिंड्रोम हो।

हमें स्ट्रिंग को विभाजित करने के लिए बदलने के लिए आवश्यक न्यूनतम वर्णों की संख्या ज्ञात करनी है।

तो यदि स्ट्रिंग "ababbc" जैसी है और k = 2, तो उत्तर 1 होगा, क्योंकि हमें दो पालिंड्रोम स्ट्रिंग में विभाजित करने के लिए एक वर्ण बदलना होगा। तो यदि हम c को b में बदलते हैं, या अंत से दूसरा b को c में, तो हमें एक पालिंड्रोम मिल सकता है जैसे "bbb" या "cbc", और दूसरा पालिंड्रोम "aba" है।

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

  • आकार 105 x 105 का एक ऐरे memo परिभाषित करें।
  • एक फंक्शन solve() परिभाषित करें, यह s, idx, k, एक 2D ऐरे dp लेगा,
  • यदि idx s के आकार के समान है, तो -
    • वापस करें जब k 0 हो तो 0 अन्यथा 1000
  • यदि memo[idx][k] -1 के बराबर नहीं है, तो -
    • memo[idx][k] वापस करें
  • यदि k <= 0, तो -
    • inf वापस करें
  • ans := inf
  • i := idx से प्रारंभ करें, जब i < s का आकार, i बढ़ाते हुए, करें -
    • ans := ans का न्यूनतम और dp[idx][i] + solve(s, i + 1, k - 1, dp) फंक्शन कॉल करें
  • memo[idx][k] = ans वापस करें
  • मुख्य विधि से, निम्न करें
  • n := s का आकार
  • memo को -1 से भरें
  • आकार n x n का एक 2D ऐरे dp परिभाषित करें
  • l := 2 से प्रारंभ करें, जब l <= n, l बढ़ाते हुए, करें -
    • i := 0, j := l - 1 से प्रारंभ करें, जब j < n, j बढ़ाते हुए, i बढ़ाते हुए, करें -
      • यदि l 2 के समान है, तो -
      • dp[i][j] := true जब s[i] s[j] के समान नहीं है
      • अन्यथा
        • dp[i][j] := dp[i + 1][j - 1] + 0 जब s[i] s[j] के समान है
  • solve(s, 0, k, dp) वापस करें

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public:    int memo[105][105];    lli solve(string s, int idx, int k, vector < vector <int> > &dp){       if(idx == s.size()) {          return k == 0? 0 : 1000;       }       if(memo[idx][k] != -1) return memo[idx][k];       if(k <= 0)return INT_MAX;       lli ans = INT_MAX;       for(int i = idx; i < s.size(); i++){          ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));       }       return memo[idx][k] = ans;    }    int palindromePartition(string s, int k) {       int n = s.size();       memset(memo, -1, sizeof(memo));       vector < vector <int> > dp(n, vector <int>(n));       for(int l =2; l <= n; l++){          for(int i = 0, j = l - 1; j <n; j++, i++){             if(l==2){                dp[i][j] = !(s[i] == s[j]);             }else{                dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);             }          }       }       return solve(s, 0, k, dp);    } }; main(){    Solution ob;    cout << (ob.palindromePartition("ababbc", 2)); }

इनपुट

“ababbc”

आउटपुट

1

  1. - C++ में पैलिंड्रोम को तोड़ना

    मान लीजिए हमारे पास एक पैलिंड्रोमिक स्ट्रिंग palindrome है, हमें इसमें ठीक एक अक्षर को किसी भी लोअरकेस अंग्रेजी अक्षर से बदलना है ताकि स्ट्रिंग लेक्सिकोग्राफिक रूप से सबसे छोटी संभव स्ट्रिंग बन जाए जो पैलिंड्रोम न हो। ऐसा करने के बाद हमें अंतिम स्ट्रिंग ढूंढनी है। यदि ऐसा करना संभव न हो, तो खाली स्ट

  1. - C++ में पैलिंड्रोम विभाजन (Palindrome Partitioning)

    मान लीजिए हमारे पास एक इनपुट स्ट्रिंग है, उस स्ट्रिंग का एक विभाजन पैलिंड्रोम विभाजन है, जब विभाजन का हर उपस्ट्रिंग एक पैलिंड्रोम हो। इस खंड में, हमें दी गई स्ट्रिंग को पैलिंड्रोम विभाजन करने के लिए आवश्यक न्यूनतम कट (minimum cuts) ढूंढने हैं। यदि स्ट्रिंग ababbbabbababa है, तो पैलिंड्रोम के रूप मे

  1. - C++ में जांचें कि संख्या पैलिंड्रोम है या नहीं

    यहां हम देखेंगे कि कैसे जांचें कि कोई संख्या पैलिंड्रोम है या नहीं। पैलिंड्रोम संख्याएं दोनों दिशाओं में समान होती हैं। उदाहरण के लिए, संख्या 12321 एक पैलिंड्रोम है, लेकिन 12345 पैलिंड्रोम नहीं है।तर्क बहुत सीधा है। हमें संख्या को उल्टा करना होगा, और यदि उल्टी संख्या वास्तविक संख्या के समान है, तो व