การเข้ารหัสสตริงเพื่อลดขนาดใน JavaScript

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับสตริงอักขระ str เป็นอาร์กิวเมนต์เดียว ฟังก์ชันของเราควรเข้ารหัสสตริงอินพุตและเปรียบเทียบขนาดกับสตริงเดิมและส่งคืนสตริงที่มีขนาดเล็กกว่า

กฎการเข้ารหัสสตริงเฉพาะคือ −

• n[s] โดยที่ s ในวงเล็บเหลี่ยมซ้ำกัน k ครั้ง

ตัวอย่างเช่น ddd สามารถเข้ารหัสเป็น 3[d] แต่ 3[d] มีความยาว 4 ในขณะที่ ddd มีความยาวเพียง 3 อักขระ ดังนั้นฟังก์ชันของเราจะคืนค่า ddd ในที่สุด

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

const str = 'aabcaabcd';

จากนั้นผลลัพธ์ควรเป็น −

const output = '2[aabc]d';

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

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