[LeetCode] 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] 的输入。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是用 stack。需要用到两个 stack，numStack 记录所有出现的数字，strStack 记录所有出现的 string。

当遇到字母的时候，先用一个 StringBuilder sb 暂时记录下来；

当遇到数字的时候，先记录数字（因为有可能不止一个 digit），记录好了之后就放入 numStack 栈保存；

当遇到左括号的时候就把 sb 放入 strStack，意思是数字之前的字符串可以先存下来，然后我们把 sb 清空，依然用 sb 去记录括号里面的内容

当遇到右括号的时候
从 strStack 中 pop 出一个元素，设为 prev，这个元素是之前已经结算好的部分
从 numStack 中 pop 出一个元素，这是左括号之前的那个乘数
比如如果乘数是 3 的话，那么我们此时需要把 sb 中的内容 append 到 prev 中三次

跑一个例子说明。比如 3[a]2[bc]。首先我遇到数字 3，我就把他放入 numStack。这里如果不止一个 digit，我们需要一位一位去看，得到那个数字，再放入 numStack。

numStack: [3]

strStack: []

res: ""

接着我遇到左括号，如果之前有字符串的部分，我就需要放入 strStack，然后生成一个新的 StringBuilder，然后用这个新的 StringBuilder 去统计括号内的部分，直到我们遇到右括号。按照这个例子，括号内我们能得到的部分就是 "a"。此时我们遇到右括号了，可以进行结算了。结算的规则是，因为有括号就意味着需要做乘法，所以我们弹出 numStack 顶端的元素（3），这是我们需要重复的次数；同时我们把 strStack 顶端的元素弹出（空），把当前括号内统计的这一段子串 append 到之前结果的尾部。这里的思路是我们每遇到一个右括号我们就把括号内的东西结算，然后 append 到之前已经结算好的部分的尾部。所以这部分做完之后

numStack: []

strStack: []

res: "aaa"

接着我们又遇到 2，将他入栈，numStack: [2]。

2 后边是个左括号，此时我们要把已经记录好的字符串入栈，避免丢失，此时

numStack: [2]

strStack: ["aaa"]

res: ""

此时我们统计2后面的字符串的部分，

numStack: [2]

strStack: ["aaa"]

res: "bc"

当我们遇到最后那个右括号的时候，我们再次做结算的动作，将 strStack 栈顶元素弹出，与当前记录好的字符串合并。res = strStack 栈顶元素 + 当前记录好的字符串。对于这个例子，就是

aaa + 2 * bc = aaa + bcbc = aaabcbc

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String decodeString(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '[') {
                strStack.push(sb.toString());
                sb = new StringBuilder();
            } else if (c == ']') {
                StringBuilder prev = new StringBuilder(strStack.pop());
                int count = numStack.pop();
                for (int j = 0; j < count; j++) {
                    prev.append(sb);
                }
                sb = prev;
            } else if (Character.isDigit(c)) {
                int num = s.charAt(i) - '0';
                while (i + 1 < n && Character.isDigit(s.charAt(i + 1))) {
                    num = num * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                numStack.push(num);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
	// corner case
	if (s === null || s.length === 0) {
		return '';
	}

	// normal case
	let numStack = [];
	let strStack = [];
	let res = '';
	let len = s.length;
	for (let i = 0; i < len; i++) {
		let c = s.charAt(i);
		if (c === '[') {
			strStack.push(res);
			res = '';
		} else if (c == ']') {
			let num = numStack.pop();
			let temp = strStack.pop();
			for (let j = 0; j < num; j++) {
				temp += res;
			}
			res = temp;
		} else if (!isNaN(c)) {
			let num = Number(c);
			while (i + 1 < len && !isNaN(s.charAt(i + 1))) {
				num = num * 10 + Number(s.charAt(i + 1));
				i++;
			}
			numStack.push(num);
		} else {
			res += c;
		}
	}
	return res;
};