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

ปัญหา

เข้ารหัสสตริงด้วยกฎ k[substring] แทน substring ที่ซ้ำ k ครั้ง เปรียบเทียบความยาว คืนสตริงที่สั้นกว่า

ตัวอย่าง

const str = 'aabcaabcd';

เข้ารหัส: '2[aabc]d' (สั้นกว่าต้นฉบับ)

โค้ดตัวอย่าง (Dynamic Programming)

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; 
      } 
    } 
  } 
  return dp[0][dp.length - 1]; 
} 
console.log(encode(str));

ผลลัพธ์

2[aabc]d