394. 字符串解码

🟠   🔖  栈 递归 字符串  🔗 力扣 LeetCode

题目

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，可以使用 栈 解决嵌套问题。

1. 初始化一个栈，用于保存未处理完的嵌套结构。
2. 使用两个变量：
   • curStr：存储当前层的字符串。
   • curNum：存储当前层的重复次数。
3. 遍历字符串，依次处理每个字符：
   • 如果是数字，更新 curNum，可能是多位数，将数字完整读取。
   • 如果是字母，累加到当前构建的字符串 curStr。
   • 如果是 [，表示新的一层嵌套，将当前的字符串和重复次数 [curStr, curNum] 压入栈中，准备处理嵌套部分。
   • 如果是 ]，表示嵌套结束，从栈中弹出上层的字符串和重复次数，将当前层的解码结果拼接到之前的结果中。
4. 遍历结束后，栈中的最终结果即为解码后的字符串。

复杂度分析

• 时间复杂度: O(n)，每个字符只被处理一次。
• 空间复杂度: O(d)，d 为嵌套深度。

代码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
	let stack = [];
	let curStr = ''; // 当前层的字符串
	let curNum = 0; // 当前层的数字

	for (let char of s) {
		if (!isNaN(char)) {
			// 当前字符是数字
			curNum = curNum * 10 + parseInt(char);
		} else if (char === '[') {
			// 遇到左括号，将当前状态保存到栈中
			stack.push([curStr, curNum]);
			curStr = ''; // 重置当前字符串
			curNum = 0; // 重置当前数字
		} else if (char === ']') {
			// 遇到右括号，处理嵌套结束
			let [prevStr, num] = stack.pop();
			curStr = prevStr + curStr.repeat(num);
		} else {
			// 当前字符是普通字母
			curStr += char;
		}
	}

	return curStr;
};

相关题目

题号	标题	题解	标签	难度	力扣
471	编码最短长度的字符串 🔒		字符串 动态规划	🔴	🀄️ 🔗
726	原子的数量		栈 哈希表 字符串 1+	🔴	🀄️ 🔗
1087	花括号展开 🔒		广度优先搜索 字符串 回溯	🟠	🀄️ 🔗