景真

外观

字符串解码

约 819 字大约 3 分钟

栈贪心

2025-02-25

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) {
        Deque<Integer> numStack = new LinkedList<>(); // 存储数字的栈，用于记录重复的次数
        Deque<String> strStack = new LinkedList<>(); // 存储字符串的栈，用于记录当前层的字符串

        String result = ""; // 当前正在构建的字符串
        int num = 0; // 用于构建数字，数字可能有多位
        
        // 遍历整个字符串
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            if (ch >= '0' && ch <= '9') {
                // 当前字符为数字，将其转换为整数部分，可能有多位数
                num = num * 10 + (ch - '0');
            } else if (ch == '[') {
                // 遇到 '[' 表示一个重复段的开始。中括号里面一定是字符，所以可以把数字入栈，为了区分中括号内外的字符串，我们需要把之前的字符串入栈。
                // 将当前的数字（即重复次数）和字符串（即前缀）推入各自的栈
                numStack.push(num);
                strStack.push(result);
                
                // 重置 num 和 result，准备解析括号内的字符串
                num = 0;
                result = "";
            } else if (ch == ']') {
                // 遇到 ']' 表示一个重复段的结束。tmp+times[result]，重点。
                // 弹出栈顶的重复次数和之前的字符串。栈顶的重复次数用于构造当前字符串，然后和栈顶字符串相加。
                int times = numStack.pop();
                String tmp = strStack.pop();
                
                // 构建当前括号内字符串的重复结果
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < times; j++) {
                    sb.append(result);
                }
                
                // 将重复后的结果与之前的字符串进行拼接。以 a3[b] 为例，tmp 是a，result是b，sb是times result，即bbb，然后result变成abbb。
                result = tmp + sb.toString();
            } else {
                // 当前字符为字母，直接添加到结果字符串中
                result += ch;
            }
        }
        
        // 返回完全解析后的字符串
        return result;
    }        
}
  • 时间复杂度：记解码后得出的字符串长度为 SS ，除了遍历一次原字符串 ss ，我们还需要将解码后的字符串中的每个字符都入栈，并最终拼接进答案中，故渐进时间复杂度为 O(S+∣s∣)O(S+|s|) ，即 O(S)O(S) 。
  • 空间复杂度：记解码后得出的字符串长度为 SS，这里用栈维护 TOKEN，栈的总大小最终与 SS 相同，故渐进空间复杂度为 O(S)O(S) 。