सी ++ में सबसे छोटी लंबाई के साथ एन्कोड स्ट्रिंग

मान लीजिए कि हमारे पास एक गैर-रिक्त स्ट्रिंग है; हमें इस स्ट्रिंग को एन्कोड करना होगा ताकि इसकी एन्कोडेड लंबाई न्यूनतम हो।

एन्कोडिंग नियम − k[encoded_string] जैसा है, जहां [] के अंदर एन्कोडेड_स्ट्रिंग को ठीक k बार दोहराया जा रहा है। हमें यह ध्यान रखना होगा कि k एक धनात्मक पूर्णांक होगा और एन्कोडेड स्ट्रिंग खाली नहीं होगी या उसमें अतिरिक्त स्थान नहीं होगा। हम मान सकते हैं कि इनपुट स्ट्रिंग में केवल लोअरकेस अक्षर हैं। यदि एन्कोडिंग प्रक्रिया स्ट्रिंग को छोटा नहीं बनाती है, तो उस स्ट्रिंग को एन्कोड न करें।

इसलिए, यदि इनपुट "आआआ" जैसा है, तो आउटपुट "5[a]" होगा क्योंकि "5[a]" 1 वर्ण से "आआआ" से छोटा है।

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

• एक 2डी सरणी डीपी परिभाषित करें

• एक फ़ंक्शन पतन () को परिभाषित करें, इसमें s, i, j,

  . लगेगा

• अस्थायी:=सूचकांक से s का विकल्प (i से j - i)

• x :=अस्थायी के साथ अस्थायी रूप से संयोजित करें

• स्थिति =x में तापमान की स्थिति

• यदि स्थिति>=तापमान का आकार, तो −

  • वापसी अस्थायी

• स्ट्रिंग के रूप में वापसी (अस्थायी / स्थिति का आकार) फिर '[' concatenate dp[i,i+pos-1]concatenate ']'

• एक फ़ंक्शन एन्कोड () को परिभाषित करें, इसमें s,

  . लगेगा

• n :=s का आकार

• dp :=n x n आकार के एक 2D सरणी को परिभाषित करें

• इनिशियलाइज़ l के लिए :=1, जब l <=n, अपडेट करें (l को 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ करने के लिए i :=0, j :=l-1, जब j

    • dp[i, j] :=इंडेक्स i से j-i तक s का सबस्ट्रिंग

    • इनिशियलाइज़ k :=i के लिए, जब k

      • अस्थायी:=डीपी [i, के] + डीपी [के + 1, जे]

      • यदि अस्थायी का आकार

        • डीपी [आई, जे]:=अस्थायी

    • प्रतिनिधि:=पतन (एस, आई, जे)

    • यदि प्रतिनिधि का आकार <=dp का आकार[i, j], तो -

      • डीपी [आई, जे]:=प्रतिनिधि

• वापसी डीपी [0, एन -1]

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector<vector<string>> dp;
   string collapse(string &s, int i, int j) {
      string temp = s.substr(i, j - i + 1);
      string x = temp + temp;
      auto pos = x.find(temp, 1);
      if (pos >= temp.size())
         return temp;
      return to_string((temp.size() / pos)) + "[" + dp[i][i + pos - 1] + "]";
   }
   string encode(string s) {
      int n = s.size();
      dp = vector<vector<string>>(n, vector<string>(n, ""));
      for (int l = 1; l <= n; l++) {
         for (int i = 0, j = l - 1; j < n; i++, j++) {
            dp[i][j] = s.substr(i, j - i + 1);
            for (int k = i; k < j; k++) {
               string temp = dp[i][k] + dp[k + 1][j];
               if (temp.size() < dp[i][j].size()) {
                  dp[i][j] = temp;
               }
            }
            string rep = collapse(s, i, j);
            if (rep.size() <= dp[i][j].size()) {
               dp[i][j] = rep;
            }
         }
      }
      return dp[0][n - 1];
   }
};
main() {
   Solution ob;
   cout << (ob.encode("bbbbbbbbbb"));
}

इनपुट

"bbbbbbbbbb"

आउटपुट

"10[b]"