JavaScript에서 크기를 줄이기 위한 인코딩 문자열

문제

문자열 str을 유일한 인수로 취하는 JavaScript 함수를 작성해야 합니다. 우리의 함수는 입력 문자열을 인코딩하고 그 크기를 원래 문자열과 비교하여 더 작은 크기의 문자열을 반환해야 합니다.

특정 문자열을 인코딩하는 규칙은 -

• 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