LeetCode 「中等」394.字符串解码
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例
输入：s = "3[a]2[bc]"
输出："aaabcbc"
输入：s = "3[a2[c]]"
输出："accaccacc"
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
解答
正则表达式
Code
/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
while (s.includes('[')) {
s = s.replace(/(\d+)\[(\w+)\]/g, (match, p1, p2) => {
return p2.repeat(+p1);
});
}
return s;
};
栈
思路
- 使用栈来处理嵌套结构
- 遍历字符串时，遇到数字和字母时直接处理
- 遇到
[时，将当前的数字和字符串压入栈中 - 遇到
]时，从栈中弹出最近的数字和字符串，并将当前字符串重复指定次数，然后拼接到之前的字符串上
- 遍历字符串
- 使用一个变量
currentNum来记录当前的数字 - 使用一个变量
currentStr来记录当前的字符串片段 - 遍历输入字符串的每个字符：
- 如果是数字，更新
currentNum - 如果是字母，直接添加到
currentStr - 如果是
[，将currentNum和currentStr压入栈中，然后重置它们 - 如果是
]，从栈中弹出最近的数字和字符串，将currentStr重复指定次数，然后拼接到弹出的字符串上
- 如果是数字，更新
- 返回最终结果
- 遍历结束后，
currentStr就是解码后的字符串
Code
/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
const stack = []; // 用于存储数字和字符串
let currentNum = 0; // 当前数字
let currentStr = ''; // 当前字符串片段
for (let i = 0; i < s.length; ++i) {
const char = s[i];
if (/\d/.test(char)) {
// 如果是数字，更新 currentNum
currentNum = currentNum * 10 + char * 1;
} else if (/[a-zA-Z]/.test(char)) {
// 如果是字母，更新 currentStr
currentStr += char;
} else if (char === '[') {
// 如果是 [，将 currentNum 和 currentStr 压入栈中
stack.push([currentNum, currentStr]);
currentNum = 0; // 重置 currentNum
currentStr = ''; // 重置 currentStr
} else if (char === ']') {
// 如果是 ]，从栈中弹出最近的数字和字符串
const [num, prevStr] = stack.pop();
// 将 currentStr 重复 num 次，并拼接到 prevStr 上
currentStr = prevStr + currentStr.repeat(num);
}
}
return currentStr;
};