递归实现:
class Solution {
public:
string decodeString(string s) {
int i = 0;
return decodeString(s,i);
}
private:
string decodeString(string s,int &i) {
string res;
while(i < s.size() && s[i]!=']')
{
if(!isdigit(s[i]))
res += s[i++];
else
{
int n = 0;
//获取数字
while(i < s.size() && isdigit(s[i]))
n = n * 10 + s[i++] - '0';
//skip [
i++;
string sub = decodeString(s,i);
//skip ]
i++;
while(n-- > 0)
res += sub;
}
}
return res;
}
};
这种实现存在一个缺陷,如果支持[a]这种输入就无法处理,leetcode的输入限制了这种,因此上面的递归实现可以AC。这道题目使用递归比较直观,相对于使用栈来说比较容易理解。
使用stack实现
class Solution {
public:
string decodeString(string s) {
string res = "";
stack <int> nums;
stack <string> strs;
int num = 0;
for(int i = 0;i < s.size();i++)
{
if(isdigit(s[i]))
num = num * 10 + s[i] -'0';
else if(isalpha(s[i]))
res += s[i];
else if(s[i] == '[')
{
nums.push(num);
num = 0;
strs.push(res);
res = "";
}
else if(s[i] == ']')
{
int cnt = nums.top();
nums.pop();
for(int i = 0;i < cnt;i++)
strs.top() += res;
res = strs.top();
strs.pop();
}
}
return res;
}
};