LeetCode.394.Decode String 字符串解码

题目描述

394 Decode String
https://leetcode-cn.com/problems/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; 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 won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

---

解题过程

由于待解码的字符串有嵌套，很容易想到用递归或栈。
第一个想法是递归，但发现递归不好写，用栈实现。

栈操作

字符不断进栈，遇到右括号 ‘]’ 就出栈拼接成一个子串，具体来说：
1、不断出栈直到遇到左括号 ‘[‘，左右括号中间的是需要重复的子串 dupStr。
2、不断出栈单个数字，倒序拼成一个整数，即先出栈的是低位，这个整数就是上一步的子串重复的次数 count。
3、子串 dupStr 重复 count 次拼接为一个字符串，再次入栈。

直到遍历完所有字符，此时栈中肯定没有数字，都已经是拼接好的子串，把栈中子串倒序拼接起来（栈底是开头、栈顶是结尾）就是结果。

注意 Java 中的 Deque 是双端队列，可重两头遍历，也就是最后可以从栈底开始不断删除元素(pollLast())

时间复杂度 O(S)，空间复杂度 O(S)，其中 S 是解码后字符串长度

private static class SolutionV202005 {
    public String decodeString(String s) {
        Deque<String> stack = new LinkedList<>();
        for (char ch : s.toCharArray()) {
            if (ch != ']') {
                // 非右括号，入栈
                stack.push(String.valueOf(ch));
            } else {
                // 遇到右括号 ]，弹出字符直到左括号 [
                StringBuilder cur = new StringBuilder();
                while (!stack.isEmpty() && !stack.peek().equals("[")) {
                    cur.insert(0, stack.pop());
                }
                stack.pop(); // 弹出 [
                int count = 0; // 重复的次数
                int radix = 1;
                // 弹出数字倒序拼成 count
                while (!stack.isEmpty()) {
                    String str = stack.peek();
                    if (str.length() == 1 && str.charAt(0) >= '0' && str.charAt(0) <= '9') {
                        count += (stack.pop().charAt(0) - '0') * radix;
                        radix *= 10;
                    } else {
                        break;
                    }
                }
                // 把 dupStr 重复 count 次，再放入栈中
                String dupStr = cur.toString();
                while (--count > 0) {
                    cur.append(dupStr);
                }
                stack.push(cur.toString());
            }
        }
        // 所有元素出栈倒序组装字符串
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.append(stack.pollLast());
        }
        return res.toString();
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_394_DecodeString.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_394_DecodeString.java

---