HHot 100C++ 图解

394. 字符串解码

一句话套路双栈处理嵌套:数字栈 + 字符串栈

题目描述

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

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

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

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

测试用例保证输出的长度不会超过 105。

 

示例 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] 

思路

时间O(输出长度)
空间O(嵌套层数 + 输出长度)(栈里存的串本身也是 O(输出))

思路

嵌套结构 -> 双栈。一个存重复次数,一个存「进入本层之前已拼好的串」。

遇 '[' 把当前 num 和当前 cur 同时压栈并清零(开新层);

遇 ']' 弹栈:cur = 上层前缀 + 本层内容 × 次数。

数字可能多位("12[a]"),所以要 num = num*10 + (c-'0') 累积。

另解

递归下降(遇 '[' 就递归)代码更短,栈空间隐式。

图解

a 0 b 1 c 2 a 3 b 4 c 5 c 6 d 7 c 8 d 9 c 10 d 11 e 12 f 13
字符串 abcabccdcdcdef(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/12_stack.cpp31 行
namespace lc0394 {
class Solution {
 public:
  string decodeString(const string& s) {
    stack<int> nums;
    stack<string> parts;
    string cur;
    int num = 0;
    for (char c : s) {
      if (isdigit((unsigned char)c)) {
        num = num * 10 + (c - '0');
      } else if (c == '[') {
        nums.push(num);   // 本层要重复几次
        parts.push(cur);  // 保存本层之前的内容
        num = 0;
        cur.clear();      // 开始收集本层内容
      } else if (c == ']') {
        string body = cur;
        int times = nums.top();
        nums.pop();
        cur = parts.top();  // 回到上一层
        parts.pop();
        for (int i = 0; i < times; ++i) cur += body;
      } else {
        cur += c;
      }
    }
    return cur;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q394_decode_string6 行
lc0394::Solution s;
CHECK_EQ(s.decodeString("3[a]2[bc]"), string("aaabcbc"));
CHECK_EQ(s.decodeString("3[a2[c]]"), string("accaccacc"));  // 嵌套
CHECK_EQ(s.decodeString("2[abc]3[cd]ef"), string("abcabccdcdcdef"));
CHECK_EQ(s.decodeString("abc3[cd]xyz"), string("abccdcdcdxyz"));
CHECK_EQ(s.decodeString("10[a]"), string("aaaaaaaaaa"));  // 多位数字

↑↓ 选择↵ 打开/ 随时唤起