LeetCode 394. 字符串解码

394. 字符串解码

解题思路

• 只要字符不是右括号 ']'，就将其压入栈中，直到遇到右括号 ']'。
• 此时需要将栈顶的字符串弹出，直到遇到左括号 '['，弹出的字符串即为需要重复的字符串。
• 接着继续弹出数字字符，计算出需要重复的次数。最后将重复后的字符串重新压入栈中。
• 当数字解析完毕之后，根据 [] 内的字符串和重复次数构造出新的字符串，并将其压入栈中。
• 最后将栈中所有字符串弹出并拼接起来即为最终结果。

示例

e.g. 输入 “3[a2[c]]”：

• 遇到 '3'，压入栈中。
• 遇到 '['，压入栈中。
• 遇到 'a'，压入栈中。
• 遇到 '2'，压入栈中。
• 遇到 '['，压入栈中。
• 遇到 'c'，压入栈中。
• 遇到 ']'，弹出 'c'，遇到 '[' 停止，得到字符串 "c" 和重复次数 2，构造出 "cc"，压入栈中。
• 遇到 ']'，弹出 "cc" 和 "a"，遇到 '[' 停止，得到字符串 "acc" 和重复次数 3，构造出 "accaccacc"，压入栈中。
• 最后将栈中所有字符串弹出并拼接起来，得到最终结果 "accaccacc"。

参考代码

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

        for(char c : s.toCharArray()) {
            if(c != ']') {
                stack.push(c);
            } else {
                // 获取括号内的字符串
                StringBuilder tmp = new StringBuilder();
                while(!stack.isEmpty() && stack.peek() != '[') {
                    tmp.append(stack.pop());
                }
                stack.pop(); // pop -> '['
                // 反转
                String tmp_ = tmp.reverse().toString();

                int num = 0;
                int base = 1;
                while(!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    num += (stack.pop() - '0') * base;
                    base *= 10;
                }
                String repeatedStr = tmp_.repeat(num);
                for(char ch : repeatedStr.toCharArray()) {
                    stack.push(ch);
                }
            }
        }
        
        StringBuilder result = new StringBuilder();
        while(!stack.isEmpty()) {
            result.append(stack.pop());
        }
        // 栈中弹出后还需要一次反转
        return result.reverse().toString();
    }
}