LeetCode-Solutions/C++/decode-string.cpp at master · pythonpeixun/LeetCode-Solutions · GitHub

32 lines (31 loc) · 812 Bytes

// Time: O(n)

// Space: O(n)

class Solution {

public:

string decodeString(string s) {

string curr;

stack<int> nums;

stack<string> strs;

int n = 0;

for (const auto& c: s) {

if (isdigit(c)) {

n = n * 10 + c - '0';

} else if (c == '[') {

nums.emplace(n);

n = 0;

strs.emplace(curr);

curr.clear();

} else if (c == ']') {

for (; nums.top() > 0; --nums.top()) {

strs.top() += curr;

}

nums.pop();

curr = strs.top();

strs.pop();

} else {

curr += c;

}

return strs.empty() ? curr : strs.top();

}

};

Expand file tree