本文最后更新于 2025-03-31T00:09:09+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| 给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: 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、创建一个 stack res 的辅助栈以及最终的返回值 string 类型的 res 初始化为空;
- 2、[ 之前的数字可能不止一位,所以要设置一个 sum 表示其之前数字的总和。
- 3、字符串题有大小写的区别,所以要注意大小写
- 4、看代码注释举例。
代码块
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| class Solution { public: string decodeString(string s) { stack<string> pos; stack<int> nums; string res = ""; int sum = 0; for(int i = 0; i < s.size(); i++) { if(isdigit(s[i])) sum = sum * 10 + s[i] - '0'; else if(isalpha(s)) res += s[i]; else if(s[i] == '[') { nums.push(sum); sum = 0; pos.push(res); res = ""; } else if(s[i] == ']') { sum = nums.top(); nums.pop(); while(sum) { pos.top() += res; sum--; } res = pos.top(); pos.pop(); } } return res; } };
|
复杂度
Day-04 394. 字符串解码
https://chaggle.github.io/2021/09/13/Leetcode/91-day/day-04/