394. Decode String
394. Decode String
题目
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string]
, where the encoded_string
inside the square brackets is being repeated exactly k
times. Note that k
is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k
. For example, there will not be input like 3a
or 2[4]
.
The test cases are generated so that the length of the output will never exceed 105
.
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Constraints:
1 <= s.length <= 30
s
consists of lowercase English letters, digits, and square brackets'[]'
.s
is guaranteed to be a valid input.- All the integers in
s
are in the range[1, 300]
.
题目大意
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string]
,表示其中方括号内部的 encoded_string
正好重复 k
次。注意 k
保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k
,例如不会出现像 3a
或 2[4]
的输入。
解题思路
本题和 第 880 题 类似。需要注意,本题中可能出现括号嵌套的情况,比如 2[a2[bc]]
,这种情况下可以先转化成 2[abcbc]
,再转化成 abcbcabcbc
,可以使用栈处理。
具体做法是:
- 遍历字符串,如果当前的字符为数位,解析出一个数字(连续的多个数位)并进栈;
- 如果当前的字符为字母或者左括号,直接进栈;
- 如果当前的字符为右括号,开始出栈,一直到左括号出栈,出栈序列反转后拼接成一个字符串,此时取出栈顶的数字,就是这个字符串应该出现的次数,根据这个次数和字符串构造出新的字符串并进栈;
- 重复如上操作,最终将栈中的元素按照从栈底到栈顶的顺序拼接起来,就得到了答案。
代码
/**
* @param {string} s
* @return {string}
*/
var decodeString = function (s) {
let stack = [];
let res = "";
let k = 0;
const isDigit = (str) => str >= "0" && str <= "9";
for (let item of s) {
if (isDigit(item)) {
k = k * 10 + Number(item);
} else if (item === "[") {
stack.push(k);
stack.push(item);
k = 0;
} else if (item === "]") {
let str = "";
while (stack[stack.length - 1] !== "[") {
str = stack.pop() + str;
}
stack.pop();
let num = stack.pop();
let repeat_str = "";
while (num > 0) {
repeat_str += str;
num--;
}
stack.push(repeat_str);
} else {
stack.push(item);
}
}
while (stack.length > 0) {
res = stack.pop() + res;
}
return res;
};
相关题目
- [🔒 Encode String with Shortest Length](https://leetcode.com/problems/encode-string-with-shortest-length)
- [726. 原子的数量](https://leetcode.com/problems/number-of-atoms)
- [🔒 Brace Expansion](https://leetcode.com/problems/brace-expansion)