Problem overview
The function decodeString receives an encoded string s and returns the decoded one. The encoding rule is k[encoded_string]: the text inside the brackets is repeated exactly k times. Plain letters outside any brackets are copied as they are. The input is always valid, digits appear only as repeat counts, and a count can have several digits, up to 300.
Take s = "3[a2[c]]". The inner part 2[c] decodes to cc, so the outer part becomes 3[acc], which decodes to accaccacc. For "2[abc]3[cd]ef" the pieces sit side by side: abcabc, then cdcdcd, then ef, giving abcabccdcdcdef.
Approach: one buffer per open bracket
Nesting is what makes this tricky. When you see 3[a2[c]] you cannot finish the outer group until the inner one is done. The group opened last is always the first one to close, and that last-in, first-out order is exactly what a stack gives you.
The lesson uses a vector<string> as the stack. Its entries come in two kinds:
- a number entry, a string of digits such as
"23", which holds a repeat count that has not been used yet; - a text entry, the decoded text collected so far at the current nesting level.
Every [ pushes a new, empty text entry. Letters are appended to the entry on top. Digits build up a number entry just below the text that will follow. A ] closes the current level: pop the text, pop the count under it, repeat the text that many times and append the result to the entry now on top, which is the enclosing level.
Here is "3[a2[c]]" traced. Each line shows the stack from bottom to top after the character is processed.
3 ["3"]
[ ["3", ""]
a ["3", "a"]
2 ["3", "a", "2"]
[ ["3", "a", "2", ""]
c ["3", "a", "2", "c"]
] ["3", "acc"]
] ["accaccacc"]
When the input ends, one entry is left, and it is the answer.
Step by step
- Create the stack: an empty
vector<string>namedstack. A vector haspush_back,backandpop_back, which is all a stack needs. - Loop over the characters of
swith a range-basedforand acharnamedc. - Opening bracket: push an empty string, the buffer for the new level.
- Letters: test with
isalpha(c). If the stack is empty, which happens for letters before any bracket, push an empty buffer first. Then appendctostack.back(). - Digits: test with
isdigit(c). Look at the top entry, or an empty string when the stack is empty. If it is not made only of digits, this is the first digit of a new count, so push it as its own entry withstring(1, c). Otherwise the count is already being built, as in23, so append the digit to it. - Closing bracket: this is the final
else. Copy the top text intocurrStrand pop it. Convert the next entry withstoiintocurrNumand pop that too. - Repeat: build
repeatedwith a counted loop that appendscurrStrcurrNumtimes. - Fold it back: if the stack is now empty,
repeatedbecomes the new bottom entry. Otherwise append it to the entry on top, which is the enclosing level's text. - Return
stack.back()after the loop.
The solution in C++
class Solution {
public:
string decodeString(string s) {
vector<string> stack;
for (char c : s) {
if (c == '[') {
stack.push_back("");
} else if (isalpha(c)) {
if (stack.empty()) {
stack.push_back("");
}
stack.back() += c;
} else if (isdigit(c)) {
string top = stack.empty() ? "" : stack.back();
if (!regex_match(top, regex("[0-9]+"))) {
stack.push_back(string(1, c));
} else {
stack.back() += c;
}
} else {
string currStr = stack.back();
stack.pop_back();
int currNum = stoi(stack.back());
stack.pop_back();
string repeated;
for (int i = 0; i < currNum; i++) {
repeated += currStr;
}
if (stack.empty()) {
stack.push_back(repeated);
} else {
stack.back() += repeated;
}
}
}
return stack.back();
}
};
A few C++ details are worth a closer look:
- Copy before you pop.
stack.back()returns a reference to the last element. Afterpop_back()that element is destroyed, so a reference to it would dangle. Writingstring currStr = stack.back();makes a real copy first. The same applies totopin the digit branch. - Building a one-character string.
string(1, c)creates a string with one copy ofc. Writingstring(c)does not compile. Appending is simpler:stack.back() += cadds acharto a string directly. - Telling numbers from text.
regex_match(top, regex("[0-9]+"))is true only if the whole string is one or more digits. An empty string fails it, which is why an empty stack or a fresh empty buffer starts a new number. This works because the input never has digits inside the text. It is also heavier than it looks: the pattern is compiled on every digit. For 30 characters that is fine, but a plain check of the first character oftopwould do the same job faster. - Parsing the count.
stoiturns"12"into theint12. Counts stop at 300, sointis plenty. - Appending in a loop.
repeated += currStrgrows the result in place, and C++ strings have no repeat operator, so the counted loop is the idiomatic way. - The final
else. It handles every character that is not[, a letter or a digit. Because the input is valid, that can only be].
Complexity
Time: about O(L · d) in the worst case, where L is the length of the output, which the lesson caps at 100,000, and d is the nesting depth. Each input character is handled once. The repeat at each ] copies text, and that text is copied again when the enclosing group appends or repeats it, so a character can be copied once per level it sits in. With inputs of at most 30 characters, d is small. The regex construction adds a constant cost per digit.
Space: O(L). The stack holds the decoded text of every open level, and the longest buffer is at most the output size.
Edge cases and common mistakes
- Multi-digit counts. In
"12[b]"the count is 12, not 1 followed by 2. Reading digits one at a time and storing each as a separate entry would break this. The digit branch extends the existing number instead. - Letters before or after a group. In
"ab2[c]d"the leadingablands in a buffer created lazily by the letter branch. Later letters append to whatever entry is on top. The decoded text isabccd. - Back-to-back groups. After
2[a]closes, the stack holds one text entry. A following digit sees that text on top, which is not all digits, and pushes a new number. So2[a]12[b]decodes toaafollowed by twelvebs. - Counts inside groups. In
"2[3[a]b]"the digit 3 arrives when the top entry is the empty buffer of the outer group. That counts as not all digits, so the 3 starts a new number. The result isaaabaaab. - Dangling references. Taking
stack.back()by reference and then callingpop_back()is undefined behaviour. Copy first. - Forgetting to pop the count. Each
]must remove two entries, the text and its number. Leaving the number behind makes the next group see a stale entry.
Testing
"3[a]2[bc]"gives"aaabcbc"."3[a2[c]]"gives"accaccacc"."2[abc]3[cd]ef"gives"abcabccdcdcdef"."abc"gives"abc", with no brackets at all."2[3[a]b]"gives"aaabaaab"."10[a]"gives tenas.