js实现decodeString
解码字符串的实现方法
在JavaScript中实现decodeString功能，通常指解码类似3[a]2[bc]这样的编码字符串，结果为aaabcbc。以下是几种实现方式：
使用栈结构处理嵌套
这种方法利用栈处理嵌套的编码字符串，适用于多层嵌套的情况。
function decodeString(s) {
const stack = [];
let currentNum = 0;
let currentStr = '';
for (let char of s) {
if (char === '[') {
stack.push(currentStr);
stack.push(currentNum);
currentStr = '';
currentNum = 0;
} else if (char === ']') {
const num = stack.pop();
const prevStr = stack.pop();
currentStr = prevStr + currentStr.repeat(num);
} else if (!isNaN(char)) {
currentNum = currentNum * 10 + parseInt(char);
} else {
currentStr += char;
}
}
return currentStr;
}示例调用：
console.log(decodeString("3[a]2[bc]")); // 输出 "aaabcbc"递归解法
对于嵌套层级较深的情况，递归方法可以更直观地处理。
function decodeString(s, index = [0]) {
let result = '';
while (index[0] < s.length && s[index[0]] !== ']') {
if (isNaN(s[index[0]])) {
result += s[index[0]++];
} else {
let num = 0;
while (!isNaN(s[index[0]])) {
num = num * 10 + parseInt(s[index[0]++]);
}
index[0]++; // 跳过 '['
const innerStr = decodeString(s, index);
index[0]++; // 跳过 ']'
result += innerStr.repeat(num);
}
}
return result;
}示例调用：
console.log(decodeString("3[a2[c]]")); // 输出 "accaccacc"正则表达式替换
通过正则表达式逐步替换编码部分，适合简单场景。
function decodeString(s) {
const regex = /(\d+)\[([a-z]*)\]/g;
while (s.includes('[')) {
s = s.replace(regex, (_, num, str) => str.repeat(num));
}
return s;
}注意事项：
- 此方法对多层嵌套的支持有限，可能需要多次替换。
性能与复杂度分析
- 栈方法：时间复杂度为O(n)，空间复杂度为O(n)，适合大多数场景。
- 递归方法：可能面临调用栈过深的问题，但代码更简洁。
- 正则方法：适合简单模式，多次替换可能影响性能。
根据实际需求选择合适的方法，栈方法通常是通用且高效的选择。
