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，可以使用栈处理。

具体做法是：

• 遍历字符串，如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈；
• 如果当前的字符为字母或者左括号，直接进栈；
• 如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字，就是这个字符串应该出现的次数；
• 根据这个次数和字符串构造出新的字符串并进栈，这里可以用二分法拼接字符串，避免超时；
• 重复如上操作，最终将栈中的元素按照从栈底到栈顶的顺序拼接起来，就得到了答案。

代码

/**
 * @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();

			stack.push(repreat(str, num));
		} else {
			stack.push(item);
		}
	}
	while (stack.length > 0) {
		res = stack.pop() + res;
	}
	return res;
};

// 二分法拼接字符串
var repreat = function (str, num) {
	let res = str,
		temp = '';
	while (num > 1) {
		if (num % 2 == 1) {
			temp += res;
		}
		res += res;
		num = (num / 2) | 0;
	}
	return res + temp;
};

相关题目

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