题目描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: 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".
算法1
(DFS) $O(k^n)$
用递归的思想来解决这个问题, 当遇到一个括号时,就将括号内的字符串截取出来作为一个新的子问题递归求解,比如对于s = "3[a2[c]]"
,我们可以将a2[c]]
作为一个新问题来求解,并将该子问题求解的结果加到上一层的答案中去。
时间复杂度
最坏情况下,假如字符串形如k[k[k[k[k[string]]]]]
这种形式,不妨设嵌套层数为n
,那么最后形成的字符串长度为 $len(string)\times k^n$ , 则时间复杂度至少与字符串的长度成正比。
C++ 代码
class Solution {
public:
string decodeString(string s) {
string ans;
for (int i = 0; i < s.size();) {
if (isdigit(s[i])) {
int j = i;
int t = 0;
while (isdigit(s[j])) {
t = t * 10 + s[j] - '0';
j ++ ;
}
i = ++ j;
int cnt = 1;
while (cnt > 0) {
if (s[j] == '[') cnt ++ ;
else if (s[j] == ']') cnt -- ;
j ++ ;
}
string res = decodeString(s.substr(i, j - i - 1));
while (t -- ) ans += res;
i = j;
} else {
ans += s[i];
i ++ ;
}
}
return ans;
}
};
算法2
(用栈模拟递归) $O(k^n)$
如果递归层数太多则上面的算法有可能会造成栈溢出,我们可以用栈来模拟上述的递归过程,每当遇到一个括号序列时,说明我们要递归进入下一层,那么我们就把该序列重复的次数num
和在该序列前已经计算好的答案字cur
分别压入栈中,当把这个括号序列处理完后,我们从两个栈的栈顶分别取出来之前的num
和cur
来计算出新的答案cur
。
时间复杂度
与递归做法时间复杂度一样。
C++ 代码
class Solution {
public:
string decodeString(string s) {
stack<int> nums;
stack<string> strs;
string cur;
int num = 0;
for (int i = 0; i < s.size(); i ++ ) {
if (s[i] == '[') {
nums.push(num);
strs.push(cur);
num = 0;
cur = "";
} else if (s[i] == ']') {
int t = nums.top();
nums.pop();
string tmp = cur;
cur = strs.top();
strs.pop();
while(t -- ) cur += tmp;
} else if (isdigit(s[i])) {
num = num * 10 + s[i] - '0';
} else {
cur += s[i];
}
}
return cur;
}
};