我正在尝试在 javascript 中实现解码字符串算法。
问题: 给定一个编码字符串,返回它的解码字符串。
编码规则为:k[encoded_string],其中方括号内的encoded_string正好重复k次。注意,k保证为正整数。
您可以假设输入的字符串总是有效的;没有额外的空格,方括号格式正确等。
此外,您可以假设原始数据不包含任何数字,并且数字仅用于那些重复数字 k。例如,不会有像 3a 或 2[4] 这样的输入。
示例 1:
输入:s = "3[a]2[bc]" 输出:“aaabcbc”
示例 2:
输入:s = "3[a2[c]]" 输出:“accaccacc”
示例 3:
输入:s = "2[abc]3[cd]ef" 输出:“abcabccdcdcdef”
示例 4:
输入:s = "abc3[cd]xyz" 输出:“abccdcdcdxyz”
我的尝试:
var decodeString = function(s) {
if(!s || s.length === 0) return "";
let map = {
'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6,
'7': 7, '8': 8, '9': 9
};
let res = "";
const dfs = (str) => {
//let res = "";
const arr = str.split("");
for(let i=0; i<arr.length; i++) {
if(arr[i] === '[') {
// call dfs
const close = getClosePos(i, arr);
dfs(arr.splice(i+1,close-(i+1)).join(""));
} else if(map[arr[i]] !== undefined) {
// repet N next letters
let k = map[arr[i]];
while(k > 0) {
res += dfs(arr.splice(i+1,arr.length).join(""));
k--;
}
} else if(arr[i] !== ']') {
res += arr[i];
}
}
//return res;
}
dfs(s);
return res;
};
const getClosePos = (i, arr) => {
for(let j=i; j<arr.length; j++) {
if(arr[j] === ']')
return j;
}
return 0;
}
我的输出是:"undefinedundefinedundefined"
谢谢
最佳答案
您可以用正则表达式替换字符串并获得所需的嵌套替换,直到没有更多字符串可用于替换。
const decodeString = string => {
let repeat
do {
repeat = false;
string = string.replace(/(\d+)\[([^\[\]]+)\]/g, (_, c, v) => {
repeat = true;
return v.repeat(c);
});
} while (repeat);
return string;
}
console.log(decodeString("3[a]2[bc]")); // "aaabcbc"
console.log(decodeString("3[a2[c]]")); // "accaccacc"
console.log(decodeString("2[abc]3[cd]ef")); // "abcabccdcdcdef"
console.log(decodeString("abc3[cd]xyz")); // "abccdcdcdxyz"
如果您想简化/更新/探索表达式,在 regex101.com 的右上面板中已对此进行了解释.您可以在this debugger link中观看匹配步骤或修改它们, 如果你有兴趣的话。调试器演示了如何 a RegEx engine可能会逐步消耗一些示例输入字符串并执行匹配过程。
正则表达式电路
jex.im可视化正则表达式:
关于javascript - 解码字符串 - Javascript,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63199096/