Problem overview
The method decodeString receives an encoded string 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, digits appear only as repeat counts, and counts can have several digits, such as 10[a].
For "3[a]2[bc]" the result is "aaabcbc". For "3[a2[c]]" the inner group makes acc, and the outer group repeats that three times: "accaccacc". For "2[abc]3[cd]ef" the result is "abcabccdcdcdef".
Approach: expand a group when its bracket closes
Nesting is the difficulty. When the scan reaches the [ of 3[a2[c]], the text of the outer group isn't finished, and then a second group starts inside it. The scan has to remember the unfinished outer group, finish the inner one, and come back. Last in, first out is exactly what a stack does.
This solution uses one stack of strings and keeps two kinds of entries in it:
- a count entry, a string of digits such as
"3", waiting for its group; - a text entry, the decoded text collected so far for the current level.
Each [ pushes an empty text entry. Letters go onto the top text entry. Digits build a count entry. A ] pops the text entry and the count entry beneath it, repeats the text, and appends the repeated text to whatever is now on top, which is the enclosing level's text.
Trace "3[a2[c]]". After 3 the stack is ["3"]. The [ adds an empty text entry: ["3", ""]. The letter a gives ["3", "a"]. The digit 2 sees a text entry on top, so it starts a new count: ["3", "a", "2"]. The next [ gives ["3", "a", "2", ""] and c fills it. The first ] pops "c" and "2", builds "cc" and appends it to "a": ["3", "acc"]. The last ] pops "acc" and "3", builds "accaccacc", and since the stack is now empty, pushes it as the only entry.
Step by step
- Create the stack as an empty array of strings. Counts are stored as strings too, so one array holds both kinds of entry.
- Loop over the characters of
s, naming each onec. - Opening bracket: push an empty string, a fresh buffer for the group's text.
- Letters: a second branch tests
c.isLetter, because letters go into the current text and never into a count. - Add the letter to the top entry. If the stack is empty (letters before any bracket), push an empty buffer first. Then append
String(c)to the last entry. - Digits: a third branch tests
c.isNumber. Digits build a count and must stay out of the decoded text. - Look at the top entry, or use an empty string when the stack is empty.
- Start a new count by pushing the digit as its own entry when the top is empty or contains something other than digits. The empty check matters because
allSatisfyistruefor an empty string, so an empty text buffer would otherwise look like a count. - Otherwise continue the count: the top already holds digits, so replace it with the top plus the new digit. This is how
23stays in one entry. - Closing bracket: the final
elsehandles the only character left,]. - Pop the group's text into
currStr. It was pushed last, so it comes off first. - Pop the count and convert it with
Int(...)!intocurrNum. The conversion returns an optional, and the unwrap is safe because the entry under a group's text is always a number. - Repeat the text with
String(repeating:count:). - Stack empty? Then the repeated text becomes the new top-level buffer.
- Otherwise append it to the top entry, folding the finished group into its enclosing level.
- Return the top entry after the loop. For valid input exactly one entry is left.
The solution in Swift
class Solution {
func decodeString(_ s: String) -> String {
var stack = [String]()
for c in s {
if c == "[" {
stack.append("")
} else if c.isLetter {
if stack.isEmpty {
stack.append("")
}
stack[stack.count - 1] += String(c)
} else if c.isNumber {
let top = stack.isEmpty ? "" : stack[stack.count - 1]
if top.isEmpty || !top.allSatisfy({ $0.isNumber }) {
stack.append(String(c))
} else {
stack[stack.count - 1] = top + String(c)
}
} else {
let currStr = stack.removeLast()
let currNum = Int(stack.removeLast())!
let repeated = String(repeating: currStr, count: currNum)
if stack.isEmpty {
stack.append(repeated)
} else {
stack[stack.count - 1] += repeated
}
}
}
return stack[stack.count - 1]
}
}
Swift details worth a closer look:
isLetterandisNumber. These are properties ofCharacter. The finalelsedoesn't test for]at all: it relies on the input being valid, so any character that is not[, a letter or a digit must be].- Appending to the last element.
stack[stack.count - 1] += String(c)modifies the stored string. ACharactercan't be added to aStringwith+=directly, which is why it is wrapped inString(c). allSatisfy.top.allSatisfy({ $0.isNumber })checks every character of the string and istruefor an empty one. The$0is the closure's first argument, here oneCharacter.- Conditional expression.
stack.isEmpty ? "" : stack[stack.count - 1]avoids indexing an empty array, which would crash. Int(...)!.Int("12")returnsInt?. It would benilfor text that isn't a number, and the!would then crash. Here the entry always holds digits.String(repeating:count:). Builds the text repeated that many times. The count is anInt, which is why the digits are converted first.removeLast(). Removes and returns the last element, so one call both reads and pops.
Complexity
Let n be the length of s and m the length of the decoded output.
Time: at least O(m + n), more for deep nesting. Each input character is handled once. Building the output costs at least its length, m. A group's text is copied once for every enclosing group that finishes, so deeply nested inputs copy more than m characters in total. The output stays small (at most 100,000 characters), so this is fine here.
Space: O(m + n). The stack holds the counts and unfinished texts, and the repeated string is built before it is appended.
Edge cases and common mistakes
- Only letters.
"ab"has no brackets. The first letter pushes an empty buffer and the result is"ab". - Letters around a group.
"ab2[c]"returns"abcc"and"a2[b]c"returns"abbc". - Multi-digit counts.
"10[a]"returns tenas. Treating each digit as its own count would break this. - Back-to-back groups. In
"2[a]3[b]"the first group leaves"aa"on the stack. The digit3sees a text entry on top, so it starts a new count instead of extending a number. The result is"aabbb". - A group that starts with a count. In
"2[3[a]]"the digit3arrives while the top entry is the empty buffer just pushed by[. Without the empty check,allSatisfywould treat that buffer as a number and glue the3onto it. With the check,3starts a new count and the result is"aaaaaa". - Using
Int(c).Int(Character("7"))doesn't compile. A character is converted withString(c)first, or withwholeNumberValue. - Popping in the wrong order. The text is popped before the count. Swapping them would try to convert a text such as
"abc"to anIntand crash.
Testing
"3[a]2[bc]"gives"aaabcbc"."3[a2[c]]"gives"accaccacc"."2[abc]3[cd]ef"gives"abcabccdcdcdef"."a2[b]c"gives"abbc"."2[a]3[b]"gives"aabbb".
