সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি ক্যারেক্টার স্ট্রিং str একমাত্র আর্গুমেন্ট হিসেবে নেবে। ফাংশনটি ইনপুট স্ট্রিংকে এনকোড করবে এবং এর আকার মূল স্ট্রিংয়ের সাথে তুলনা করবে; যেটি ছোট হবে সেটি রিটার্ন করবে।
এনকোডিং নিয়ম:
n[s], যেখানে স্কোয়ার ব্র্যাকেটের ভিতরেরsঠিকkবার রিপিট হয়েছে।
উদাহরণস্বরূপ, ddd কে 3[d] এনকোড করা যায় কিন্তু 3[d]-র দৈর্ঘ্য ৪ যখন ddd শুধু ৩ ক্যারেক্টার। তাই ফাংশন ddd রিটার্ন করবে।
উদাহরণ:
const str = 'aabcaabcd';
আউটপুট হবে:
const output = '2[aabc]d';
উদাহরণ
কোডটি নিচের মতো (DP):
const str = 'aabcaabcd'; function encode(s) { const { length } = s; const dp = Array(length).fill([]); dp.forEach((el, ind) => { dp[ind] = Array(length).fill(null); }); for(let l = 1; l <= length; l++){ for(let i = 0; i + l <= length; i++){ let j = i + l - 1; dp[i][j] = s.substring(i, j + 1); for (let k = i; k < j ; k ++) { let acc = dp[i][k] + dp[k + 1][j]; if (acc.length < dp[i][j].length) { dp[i][j] = acc; } } let sub = s.substring(i, j + 1); let double = sub + sub; let cut = double.indexOf(sub, 1); if (cut != -1 && cut < sub.length) { let acc = sub.length / cut + "[" + dp[i][i + cut - 1] +"]"; if (acc.length < dp[i][j].length) { dp[i][j] = acc; } } } } let res = dp[0][dp.length - 1]; return res; } console.log(encode(str)); আউটপুট
কনসোলে আউটপুট:
2[aabc]d
