【LeetCode】394.字符串解码-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】394.字符串解码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1, 300]

解答

源代码

class Solution {
    public String decodeString(String s) {
        LinkedList<Character> stack = new LinkedList<>();

        for (char ch : s.toCharArray()) {
            if (ch != ']') {
                stack.offerLast(ch);
            } else {
                StringBuilder sb = new StringBuilder();

                // 1. 将"["之前的字符都出栈
                while (stack.peekLast() != '[') {
                    sb.insert(0, stack.pollLast());
                }

                String str = sb.toString();

                // 将"["出栈
                stack.pollLast();

                // 2. 将数字字符出栈
                sb = new StringBuilder();
                while (!stack.isEmpty() && Character.isDigit(stack.peekLast())) {
                    sb.insert(0, stack.pollLast());
                }
                int num = Integer.parseInt(sb.toString());

                // 3. 进行解码 
                sb = new StringBuilder();
                while (num > 0) {
                    sb.append(str);
                    num--;
                }
                
                // 4. 将解码后的字符都放入栈中
                for (char c : sb.toString().toCharArray()) {
                    stack.offerLast(c);
                }
            }
        }

        // 将栈中解码后的字符都拿出来
        StringBuilder code = new StringBuilder();
        while (!stack.isEmpty()) {
            code.insert(0, stack.pollLast());
        }

        return code.toString();
    }
}