Problem overview
The method DecodeString receives an encoded string s and returns the decoded one. The rule is k[encoded_string]: the text inside the brackets is repeated exactly k times. Groups can be nested, and plain letters can appear before, between and after groups. The input is always valid, and digits appear only as repeat counts, so input like 3a or 2[4] never occurs.
Take 3[a2[c]]. The inner group 2[c] becomes cc. The outer group then repeats acc three times, which gives accaccacc. For 2[abc]3[cd]ef the groups sit side by side, and the answer is abcabc + cdcdcd + ef, which is abcabccdcdcdef.
Approach: finish the innermost group first
Nesting is the whole difficulty. When the scan reaches a ], the group that just closed is always the innermost one that is still open. Its text is complete, and the count that goes with it was read just before its [. So the plan is to remember counts and partial texts in the order they were opened, and to resolve the most recent one first. That is last in, first out, which is a stack.
This lesson keeps a single List<string> as the stack, holding two kinds of entries side by side: a count (kept as a string of digits) and a text buffer. For 3[a2[c]] the stack grows like this while the scan runs:
| Character read | Stack afterwards |
|---|---|
3 | ["3"] |
[ | ["3", ""] |
a | ["3", "a"] |
2 | ["3", "a", "2"] |
[ | ["3", "a", "2", ""] |
c | ["3", "a", "2", "c"] |
] | ["3", "acc"] |
] | ["accaccacc"] |
At the first ] the top is the buffer c and under it sits the count 2. Both are removed, the repetition cc is built, and it is appended to the buffer that is now on top. That buffer, a, becomes acc. The second ] repeats it three times, and since nothing is left under it, the result becomes the only entry.
Step by step
- Create the stack as an empty
List<string>namedstack. Each[will open a new buffer, and counts and decoded text will be separate entries. - Loop over the characters of
swithforeach (char c in s). Every character is a bracket, a digit or a letter, and each needs its own treatment. - Handle
[. Add an empty string. The text inside the brackets will be collected there. - Handle letters with
char.IsLetter. A letter belongs to the current text, never to a count. - Append the letter to the last entry. If the stack is empty, as it is for letters before any bracket, add an empty buffer first so that the letter has somewhere to go.
- Handle digits with
char.IsDigit. Digits build the repeat count and must stay apart from decoded text. - Look at the top. Store the last entry in
top, or an empty string when the stack is empty. - Start or continue a count. If
topis empty or is not made only of digits, this digit begins a new count, so push it as its own entry. The emptiness check matters becauseAllreturnstruefor an empty string, and an empty buffer just opened by[must not be mistaken for a number. - Otherwise append the digit to the top. This is how
23in23[a]ends up as one entry instead of two. - Handle
]in the finalelse: anything left over is a closing bracket, so one group is finished. - Pop the text. Copy the last entry into
currStr, then callRemoveAt.RemoveAtreturns nothing, so the value has to be read first. - Pop the count. The new last entry is the number. Convert it with
int.ParseintocurrNumand remove it as well. - Expand the group by repeating
currStrcurrNumtimes and joining the pieces. - Put the result back. If the stack is now empty, the expansion becomes the new outermost buffer. Otherwise append it to the last entry, which folds the finished group into the text one level up.
- Return the last entry. For valid input exactly one buffer remains, and it is the whole answer.
The solution in C#
class Solution {
public string DecodeString(string s) {
List<string> stack = new List<string>();
foreach (char c in s) {
if (c == '[') {
stack.Add("");
} else if (char.IsLetter(c)) {
if (stack.Count == 0) {
stack.Add("");
}
stack[stack.Count - 1] += c;
} else if (char.IsDigit(c)) {
string top = stack.Count == 0 ? "" : stack[stack.Count - 1];
if (top.Length == 0 || !top.All(char.IsDigit)) {
stack.Add(c.ToString());
} else {
stack[stack.Count - 1] += c;
}
} else {
string currStr = stack[stack.Count - 1];
stack.RemoveAt(stack.Count - 1);
int currNum = int.Parse(stack[stack.Count - 1]);
stack.RemoveAt(stack.Count - 1);
string repeated = string.Concat(Enumerable.Repeat(currStr, currNum));
if (stack.Count == 0) {
stack.Add(repeated);
} else {
stack[stack.Count - 1] += repeated;
}
}
}
return stack[stack.Count - 1];
}
}
Some C# details are worth knowing here:
using System.Linq;is needed forAllandEnumerable.Repeat. Astringis a sequence ofcharvalues, which is whytop.All(char.IsDigit)compiles: the method groupchar.IsDigitis used as the test for each character.string.Concat(Enumerable.Repeat(currStr, currNum))creates a sequence that containscurrStrcurrNumtimes and joins it into one string.string.Concataccepts any sequence of strings.stack[stack.Count - 1] += cappends acharto a string. Strings are immutable, so this builds a new string and stores it back in the list slot. That is fine at this size, with at most 30 input characters.c.ToString()turns the digit character into a one-character string, because the list holds strings.- Counts are strings. Keeping them as digit strings lets one
List<string>hold everything, andint.Parseconverts the count back only when its group closes. Counts go up to 300, so anintis more than enough. - No
Stack<T>here. The solution uses a list because it appends to the last entry in place, which aStack<string>does not allow without popping and pushing.
Complexity
Let n be the length of the output, which the tests keep at or below 100,000. Each repetition builds a string no longer than the final answer, and every character of the output is copied a small number of times, once for each nesting level it passes through while the groups fold outwards. So the work is proportional to the output size times the nesting depth, and with a 30-character input that depth is small. The extra memory is proportional to the output size, because the buffers hold decoded text.
Edge cases and common mistakes
- Multi-digit counts.
10[x]must give ten x characters. Treating each digit as its own count would produce the wrong answer, which is why a digit is appended to the top when the top is already a count. - Letters before the first bracket. In
ab3[c]the lettersabform a buffer with no bracket opening it. The empty-stack check in the letter branch creates it, and the result isabccc. - Letters after a group. In
2[abc]3[cd]efthe finalefis appended to the buffer holding the decoded groups. - A group directly inside a group. In
2[3[a]b]the inner group is folded into the outer buffer first, and thenbis appended, givingaaabaaab. The opening bracket of the outer group leaves an empty buffer on the stack, and that is exactly why the digit branch must not treat an empty top as a number. - Reading before removing. Calling
RemoveAtbefore copying the entry loses the text.List<T>has no pop method that returns the removed item. - Using
char.IsLetterfor brackets. The closing bracket falls into the finalelse, so the order of the branches matters:[first, then letters, then digits, then everything else.
Testing
"3[a]2[bc]"gives"aaabcbc"."3[a2[c]]"gives"accaccacc"."2[abc]3[cd]ef"gives"abcabccdcdcdef"."ab3[c]"gives"abccc"."10[x]"gives"xxxxxxxxxx"."2[3[a]b]"gives"aaabaaab".