在 JavaScript 中对字符串进行编码以减小其大小
javascriptweb developmentfront end technology
问题
我们需要编写一个 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
