数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究编码字符串以缩小其在 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
更新于：04-Mar-2021
985 浏览
广告