ধরুন আমাদের একটি অ-খালি স্ট্রিং আছে; আমাদের এই স্ট্রিংটিকে এমনভাবে এনকোড করতে হবে যাতে এর এনকোড করা দৈর্ঘ্য সর্বনিম্ন হয়।
এনকোডিং নিয়ম হল −k[এনকোডেড_স্ট্রিং] এর মত, যেখানে এনকোডেড_স্ট্রিং [ ] এর ভিতরে ঠিক k বার পুনরাবৃত্তি হচ্ছে। আমাদের মনে রাখতে হবে যে k একটি ধনাত্মক পূর্ণসংখ্যা হবে এবং এনকোড করা স্ট্রিং খালি থাকবে না বা অতিরিক্ত স্থান থাকবে না। আমরা অনুমান করতে পারি যে ইনপুট স্ট্রিংটিতে শুধুমাত্র ছোট হাতের অক্ষর রয়েছে। যদি এনকোডিং প্রক্রিয়া স্ট্রিংটিকে ছোট না করে, তাহলে সেই স্ট্রিংটিকে এনকোড করবেন না।
সুতরাং, যদি ইনপুটটি "aaaaa" এর মত হয়, তাহলে আউটপুট হবে "5[a]" কারণ "5[a]" 1 অক্ষর দ্বারা "aaaaa" থেকে ছোট।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি 2D অ্যারে ডিপি
সংজ্ঞায়িত করুন -
একটি ফাংশন সংজ্ঞায়িত করুন(), এটি s, i, j,
লাগবে -
temp :=সূচক থেকে s এর সাবস্ট্রিং (i থেকে j - i)
-
x :=temp এর সাথে temp concatenate
-
pos =x
-এ তাপমাত্রার অবস্থান -
যদি pos>=তাপমাত্রার আকার হয়, তাহলে −
-
রিটার্ন টেম্প
-
-
স্ট্রিং হিসাবে (টেম্প / pos-এর আকার) ফেরত দিন তারপর '[' 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
-
তাপমাত্রা :=dp[i, k] + dp[k + 1, j]
-
যদি তাপমাত্রার আকার
-
dp[i, j] :=temp
-
-
-
rep :=পতন(s, i, j)
-
যদি প্রতিনিধির আকার <=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]"
