图片.png
图片.png
这个题吧，用dfs还是很简单的。将括号里面的一切当成另一个崭新的dfs. 大循环里面 要么是string 要么是数字
dfs:
//dfs:
string decode(string s, int& i) {
string res = "";
int n = s.size();
while (i < n && s[i] != ']') {
if (s[i] < '0' || s[i] > '9') {
res += s[i++];
}
else {
int cnt = 0;
while (s[i] >= '0' && s[i] <= '9') {
cnt = cnt * 10 + s[i++] - '0';
}
++i;
string t = decode(s, i);
++i;
while (cnt-- > 0) {
res += t;
}
}
}
return res;
}
string decodeString(string s) {
int i = 0;
return decode(s, i);
}
stack:
//my
class Solution {
public:
string decodeString(string s) {
stack<int> num;
stack<string> data;
int i = 0; int n = s.size(); int cnt = 0;
string temp = "";
while (i < n) {
if (s[i] >= '0' && s[i] <= '9') {
cnt = cnt * 10 + s[i] - '0';
}
else if (s[i] == '[') {
num.push(cnt);
data.push(temp);
cnt = 0; temp = "";
}
else if (s[i] == ']') {
int n = num.top(); num.pop();
for (int i = 0; i < n; i++)
data.top() += temp;
temp = data.top();
data.pop();
}
else {
temp += s[i];
}
i++;
}
return data.empty() ? temp : data.top();
}
};
