Mã hóa chuỗi để giảm kích thước của nó trong JavaScript

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript có một chuỗi ký tự, str, làm đối số duy nhất. Hàm của chúng ta phải mã hóa chuỗi đầu vào và so sánh kích thước của nó với chuỗi ban đầu và trả về chuỗi có kích thước nhỏ hơn.

Quy tắc để mã hóa một chuỗi cụ thể là -

• n [s], trong đó các s bên trong dấu ngoặc vuông được lặp lại đúng k lần.

Ví dụ:ddd có thể được mã hóa thành 3 [d] nhưng 3 [d] có độ dài 4 trong khi ddd chỉ dài 3 ký tự nên hàm của chúng ta cuối cùng sẽ trả về ddd.

Ví dụ:nếu đầu vào của hàm là -

const str = 'aabcaabcd';

Sau đó, đầu ra phải là -

const output = '2[aabc]d';

Ví dụ

Mã cho điều này sẽ là -

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));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

2[aabc]d