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 square brackets is repeated exactly k times. Groups can be nested, and plain letters may appear between and around them. The input is always valid, and digits appear only as repeat counts.
For "3[a]2[bc]" the result is "aaabcbc": "a" three times, then "bc" twice. For "3[a2[c]]" the inner group gives "cc", the outer text becomes "acc", and three copies of it make "accaccacc". For "2[abc]3[cd]ef" the result is "abcabccdcdcdef".
Approach: finish the inside before the outside
A group can't be expanded until its closing bracket arrives, because everything inside it, nested groups included, must be decoded first. This is a job for a stack: inner work is on top, and finishing it hands a result down to the enclosing level.
The solution keeps one stack of strings, and each entry is either a count or a piece of text:
- A
[pushes an empty string, a new buffer for the text inside the bracket. - A letter is appended to the top buffer.
- A digit builds a count. The first digit pushes a new entry, and further digits are appended to that same entry, so
23is one entry and not two. - A
]pops the finished text, pops the count beneath it, repeats the text and appends the result to whatever is now on top.
Every [ is preceded by its count, so when a ] arrives the stack ends with count, text. Here is the stack after each character of "3[a2[c]]":
3 ["3"]
[ ["3", ""]
a ["3", "a"]
2 ["3", "a", "2"]
[ ["3", "a", "2", ""]
c ["3", "a", "2", "c"]
] ["3", "acc"]
] ["accaccacc"]
The first ] pops "c" and "2" and appends "cc" to "a". The second pops "acc" and "3". The stack is then empty, so the repeated text becomes the only entry.
Step by step
- Create the stack as a
valbound to an emptyArrayBuffer[String]. The last element is the top. - Loop over the characters with
for (c <- s). - Handle
[. Push an empty string withstack += "". - Handle letters with
c.isLetter. If the stack is empty, push an empty string first, so letters before any bracket have a buffer. Then appendcto the last entry. - Handle digits with
c.isDigit. Read the top entry intotop, or""when the stack is empty. - Start or continue a count. If
topis not made only of digits, whichtop.matches("\\d+")tests, a new count begins, so pushc.toString. Otherwise append the digit to the last entry. - Handle
]in the finalelse. Remove the last entry intocurrStr, then remove the next one and convert it withtoIntintocurrNum. - Repeat the text with
currStr * currNum. - Put the result back. If the stack is now empty, push the repeated text. Otherwise append it to the last entry, which folds it into the enclosing level.
- Return the last entry of the stack. For valid input exactly one entry is left: the whole decoded string.
The solution in Scala
class Solution {
def decodeString(s: String): String = {
val stack = scala.collection.mutable.ArrayBuffer[String]()
for (c <- s) {
if (c == '[') {
stack += ""
} else if (c.isLetter) {
if (stack.isEmpty) {
stack += ""
}
stack(stack.length - 1) += c
} else if (c.isDigit) {
val top = if (stack.isEmpty) "" else stack(stack.length - 1)
if (!top.matches("\\d+")) {
stack += c.toString
} else {
stack(stack.length - 1) += c
}
} else {
val currStr = stack.remove(stack.length - 1)
val currNum = stack.remove(stack.length - 1).toInt
val repeated = currStr * currNum
if (stack.isEmpty) {
stack += repeated
} else {
stack(stack.length - 1) += repeated
}
}
}
stack(stack.length - 1)
}
}
Scala details:
stack(i) += cworks on a buffer element. It is shorthand forstack(i) = stack(i) + c: a string plus aChargives a new string, which is stored back into the slot.- Multiplying a string.
currStr * currNumrepeats the stringcurrNumtimes. It comes from Scala's string extension methods, and"ab" * 3is"ababab". A count of 0 gives the empty string. matchestests the whole string."12".matches("\\d+")is true, while""and"a1"give false. The empty string fails because+demands at least one digit, which is what makes the stand-in""for an empty stack safe. In an ordinary string literal the regular expression needs the doubled backslash.ifis an expression.val top = if (stack.isEmpty) "" else stack(stack.length - 1)is Scala's replacement for a ternary operator.remove(index)returns the element it removes, so a single call reads and pops.- Last expression. The method ends with
stack(stack.length - 1), which is its result without areturn.
Complexity
Time: proportional to the length of the decoded output plus the cost of copying strings. Each ] builds the repeated string once, and strings are copied again as groups are folded into their parents. Nested groups can copy an inner result once per level, so the work is bounded by the output length times the nesting depth, which stays small for the limits here.
Space: O(L), where L is the length of the decoded output, since the final string is built in the stack. The number of entries is at most about twice the nesting depth, plus one.
Edge cases and common mistakes
- Multi-digit counts.
"10[a]"returns"aaaaaaaaaa". The digit0is appended to the entry"1"because that entry is all digits. - Letters around groups.
"2[a]bc"returns"aabc", and"ab2[c]d"returns"abccd". A digit after text starts a new count entry, because the top is text and not digits. - Plain text.
"abc"returns"abc": the first letter pushes the buffer. - Deep nesting.
"2[2[2[a]]]"returns"aaaaaaaa". - Empty group.
"12[]"returns the empty string. - Popping in the wrong order. The text is on top and the count is beneath it. Reading the count first would try to convert the text to a number.
- Treating a digit as a count when it continues the previous one. Pushing every digit as its own entry turns
"12[a]"into a stack that has no single count to pop. - Parsing a count with
c.toInt. On aChar,toIntgives its character code, not its digit value:'3'.toIntis 51. The solution avoids this by building the count as a string and converting the whole string.
Testing
"3[a]2[bc]"returns"aaabcbc"."3[a2[c]]"returns"accaccacc"."2[abc]3[cd]ef"returns"abcabccdcdcdef"."ab2[c]d"returns"abccd".
