सी++ में अजीब प्रिंटर

मान लीजिए कोई अजीब प्रिंटर है इसकी कुछ आवश्यकताएं हैं -

• प्रिंटर हर बार केवल उसी वर्ण का एक क्रम प्रिंट कर सकता है।
• प्रत्येक मोड़ में, प्रिंटर किसी भी स्थान से शुरू और समाप्त होने वाले नए वर्णों को प्रिंट कर सकता है, और मूल मौजूदा वर्णों को कवर करेगा।

इसलिए यदि हमारे पास एक स्ट्रिंग है जिसमें निचले अक्षर होते हैं, तो हमारा काम प्रिंटर को प्रिंट करने के लिए आवश्यक न्यूनतम घुमावों की गणना करना है।

तो अगर इनपुट "आबाबा" जैसा है, तो इसमें 2 मोड़ लगेंगे, पहले आआआ को प्रिंट करता है और फिर अक्षरों को बदलकर बी प्रिंट करता है।

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

• n :=आकार का
• यदि n 0 के समान है, तो:वापसी 0
• क्रम n x n के एक 2D सरणी dp को परिभाषित करें, इसे अनंत से भरें
• इनिशियलाइज़ l :=1 के लिए, जब l <=n, अपडेट करें (l को 1 से बढ़ाएँ), −
  करें
  • इनिशियलाइज़ करने के लिए i :=0, j :=l-1, जब j
  • यदि l 1 के समान है, तो:dp[i, j] :=1
• अन्यथा जब l 2 के समान हो, तो −
  • dp[i, j] :=1 जब s[i] s[j] के समान हो अन्यथा 2
• अन्यथा
  • इनिशियलाइज़ k :=i के लिए, जब k करें
  • अस्थायी:=dp[i, k] + dp[k + 1, j]
  • dp[i, j] :=न्यूनतम dp[i, j] और (temp – 1 जब s[k] s[j] के समान हो अन्यथा अस्थायी।

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
   int strangePrinter(string s) {
      int n = s.size();
      if(n == 0) return 0;
      vector < vector <int> > dp(n, vector <int>(n, INF));
      for(int l = 1; l <= n; l++){
      for(int i = 0, j = l - 1; j < n; i++, j++){
         if(l == 1){
            dp[i][j] = 1;
            }else if(l == 2){
               dp[i][j] = s[i] == s[j] ? 1 : 2;
            }else{
               for(int k = i; k < j; k++){
                  int temp = dp[i][k] + dp[k + 1][j];
                  dp[i][j] = min(dp[i][j], s[k] == s[j] ? temp - 1: temp);
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.strangePrinter("aaabba"));
}

इनपुट

“2*”

आउटपुट

2