मान लीजिए हमारे पास एक गैर-खाली स्ट्रिंग है; हमें इस स्ट्रिंग को एनकोड करना है ताकि इसकी एनकोडेड लंबाई न्यूनतम हो।
एनकोडिंग नियम इस प्रकार है − k[encoded_string], जहां [ ] के अंदर encoded_string को ठीक k बार दोहराया जा रहा है। हमें ध्यान रखना होगा कि k एक धनात्मक पूर्णांक होगा और एनकोडेड स्ट्रिंग खाली नहीं होगी या इसमें अतिरिक्त स्पेस नहीं होगा। हम मान सकते हैं कि इनपुट स्ट्रिंग में केवल लोअरकेस अक्षर हैं। यदि एनकोडिंग प्रक्रिया स्ट्रिंग को छोटा नहीं बनाती है, तो उस स्ट्रिंग को एनकोड न करें।
तो, यदि इनपुट "aaaaa" जैसा है, तो आउटपुट "5[a]" होगा क्योंकि "5[a]" "aaaaa" से 1 वर्ण छोटा है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
एक 2D ऐरे dp परिभाषित करें
collapse() नामक एक फ़ंक्शन परिभाषित करें, जो s, i, j लेगा,
temp := इंडेक्स (i से j - i) से s का सबस्ट्रिंग
x := temp को temp के साथ जोड़ें
pos = x में temp की स्थिति
यदि pos >= temp का आकार, तो −
temp लौटाएं
(temp का आकार / pos) को स्ट्रिंग के रूप में लौटाएं फिर '[' जोड़ें फिर dp[i,i+pos-1] जोड़ें फिर ']'
encode() नामक एक फ़ंक्शन परिभाषित करें, जो s लेगा,
n := s का आकार
dp := आकार n x n का एक 2D ऐरे परिभाषित करें
l := 1 से आरंभ करें, जब l <= n, अद्यतन करें (l को 1 से बढ़ाएं), करें −
i := 0, j := l - 1 से आरंभ करें, जब j < n, अद्यतन करें (i को 1 से बढ़ाएं), (j को 1 से बढ़ाएं), करें −
dp[i, j] := इंडेक्स i से j - i तक s का सबस्ट्रिंग
k := i से आरंभ करें, जब k < j, अद्यतन करें (k को 1 से बढ़ाएं), करें −
temp := dp[i, k] + dp[k + 1, j]
यदि temp का आकार < dp[i, j] का आकार, तो −
dp[i, j] := temp
rep := collapse(s, i, j)
यदि rep का आकार <= dp[i, j] का आकार, तो −
dp[i, j] := rep
dp[0, n - 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]"
