資料結構
網路
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 瀏覽
廣告