题目描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string]
,表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a
或 2[4]
的输入。
示例:
s = “3[a]2[bc]”, 返回 “aaabcbc”.
s = “3[a2[c]]”, 返回 “accaccacc”.
s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.
解题思路
解法一:栈
因为括号会有嵌套,所以我们采用栈来首先处理内部,再处理外部。具体规则为:
- 当遇到数字时,将连续的数字解析完并入栈
- 当遇到左括号或者字母时,直接入栈
- 当遇到右括号时,连续出栈直到遇到左括号。将出栈得到的序列反转,并再出栈得到一个重复次数,构造得到新的字符串并入栈
Python 3.6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution: def decodeString(self, s: str) -> str: stack = [] count = "" for char in s: if char.isdigit(): count += char elif char == "[": stack.append(int(count)) count = "" stack.append("[") elif char == "]": cur_str = [] cur_char = "" while cur_char != "[": cur_str.append(cur_char) cur_char = stack.pop() num = stack.pop() cur_str.reverse() stack.append(num * "".join(cur_str)) else: stack.append(char) return "".join(stack)
|
执行用时:44 ms
内存消耗:13.6 MB
C++
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 39 40 41 42 43 44 45 46 47 48 49
| class Solution { public: string getDigit(string& s, size_t& ptr) { string num = ""; while (isdigit(s[ptr])) { num.push_back(s[ptr++]); } return num; }
string getString(vector<string>& stack) { string res; for (const auto &i : stack) { res += i; } return res; }
string decodeString(string s) { vector<string> stack; size_t ptr = 0; while (ptr < s.size()) { char cur_char = s[ptr]; if (isdigit(cur_char)) { string count = getDigit(s, ptr); stack.push_back(count); } else if (isalpha(cur_char) || cur_char == '[') { stack.push_back(string(1, s[ptr++])); } else { ++ptr; vector<string> sub; while (stack.back() != "[") { sub.push_back(stack.back()); stack.pop_back(); } reverse(sub.begin(), sub.end()); stack.pop_back(); int repeat = stoi(stack.back()); stack.pop_back(); string cur_str = getString(sub); string final_str = ""; while (repeat--) final_str += cur_str; stack.push_back(final_str); } } return getString(stack); } };
|
执行用时:0 ms
内存消耗:6.8 MB
解法二:递归
- 当遇到数字时,将该数字连续解析出来
- 当遇到左括号时,开始递归,并将结果重复多次计入结果变量
- 当遇到右括号时,返回当前结果以及索引值
Python 3.6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution: def decodeString(self, s: str) -> str: def dfs(s, idx): res, repeat = "", 0 while idx < len(s): if s[idx].isdigit(): repeat = 10 * repeat + int(s[idx]) elif s[idx] == "[": idx, tmp = dfs(s, idx + 1) res += repeat * tmp repeat = 0 elif s[idx] == "]": return idx, res else: res += s[idx] idx += 1 return res
return dfs(s, 0)
|
执行用时:40 ms
内存消耗:13.5 MB
C++
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
| class Solution { public: string dfs(string& s, size_t& i) { string res = ""; int repeat = 0; while (i < s.size()) { if (isdigit(s[i])) { repeat = 10 * repeat + (s[i] - '0'); } else if (s[i] == '[') { string tmp = dfs(s, ++i); while (repeat) { res += tmp; --repeat; } } else if (s[i] == ']') { return res; } else { res += string(1, s[i]); } ++i; } return res; }
string decodeString(string s) { size_t i = 0; return dfs(s, i); } };
|
执行用时:0 ms
内存消耗:6.5 MB
参考
https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/
https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/