Problem overview
The function decodeString receives an encoded string and returns the decoded one. The rule is k[encoded_string]: the text inside the square brackets is repeated exactly k times, where k is a positive integer. Groups can be nested, and plain letters can appear before, between and after them. Digits appear only as repeat counts, so inputs like 3a or 2[4] don't occur. The input is always valid, is at most 30 characters long, and every count is between 1 and 300.
For "3[a2[c]]" the inner group 2[c] becomes cc, so the outer group is 3[acc], which gives "accaccacc". For "2[abc]3[cd]ef" the result is abcabc, then cdcdcd, then the loose ef: "abcabccdcdcdef".
Approach: one stack holding counts and text
Nesting means the string must be decoded from the inside out, and a stack is the natural tool. The solution puts two kinds of entries on one stack, both stored as strings: a count (digits) and a text buffer. Read left to right:
- A
[opens a new empty text buffer. The count that came just before it is already on the stack, right below. - A letter is added to the buffer on top.
- A digit extends the count on top, or starts a new count entry if the top isn't a number.
- A
]closes a group: pop the text, pop the count below it, repeat the text that many times, and add the result to whatever is now on top.
Because a closed group is added to the buffer one level up, nested groups are expanded before the groups that contain them. At the end, a single buffer remains with the whole answer.
An alternative uses two separate stacks, one for counts and one for text. This lesson keeps a single stack of strings and tells the two kinds of entry apart by whether strconv.Atoi can parse the top.
Step by step
- Create the stack as an empty
[]string. - Loop over the runes of
swithrange, naming each onec. - On
[, append an empty string: a fresh buffer for the bracketed text. - Add an
else iffor letters withunicode.IsLetter. - Handle a letter. If the stack is empty, a letter outside every bracket has no buffer yet, so append an empty one. Then add
string(c)to the last entry. - Add an
else iffor digits withunicode.IsDigit. - Peek at the top. Declare
topas""and overwrite it with the last entry when the stack isn't empty. Go has no ternary operator, so this takes anif. - Start a new count when
strconv.Atoi(top)fails: the top is text (or empty), so this digit begins a number. Appendstring(c)as a new entry. - Continue the count otherwise: the top already holds digits, so add the new digit to it. This is how
23stays in one entry. - Add the final
else. The only character left is]. - Pop the text into
currStrby reslicing. - Pop the count: parse the new last entry with
strconv.AtoiintocurrNum, ignoring the error, and reslice again. - Repeat the text with
strings.Repeat(currStr, currNum). - Place the result. If the stack is now empty, push
repeatedas the outermost buffer. - Otherwise append it to the last entry, folding the group into the level above.
- Return the last entry. For valid input exactly one remains.
The solution in Go
func decodeString(s string) string {
stack := []string{}
for _, c := range s {
if c == '[' {
stack = append(stack, "")
} else if unicode.IsLetter(c) {
if len(stack) == 0 {
stack = append(stack, "")
}
stack[len(stack)-1] += string(c)
} else if unicode.IsDigit(c) {
top := ""
if len(stack) > 0 {
top = stack[len(stack)-1]
}
if _, err := strconv.Atoi(top); err != nil {
stack = append(stack, string(c))
} else {
stack[len(stack)-1] += string(c)
}
} else {
currStr := stack[len(stack)-1]
stack = stack[:len(stack)-1]
currNum, _ := strconv.Atoi(stack[len(stack)-1])
stack = stack[:len(stack)-1]
repeated := strings.Repeat(currStr, currNum)
if len(stack) == 0 {
stack = append(stack, repeated)
} else {
stack[len(stack)-1] += repeated
}
}
}
return stack[len(stack)-1]
}
The solution uses the unicode, strconv and strings packages. The Go details worth a closer look:
- Runes and
string(c). Ranging over a string yields runes, soc == '['compares a rune with a rune constant.string(c)turns the rune into a one-character string; the rune 97 becomes"a". - The error is the test.
strconv.Atoireturns(int, error). It fails on both a non-numeric string such as"abc"and the empty string. The digit branch relies on this: failure means "no count is being built right now". - The ignored error. In the
]branch the entry below the text always holds digits, socurrNum, _ :=discards an error that can't happen for valid input. - Short
ifstatements.if _, err := strconv.Atoi(top); err != nildeclareserrfor thatifand itselseonly. - Pop by reslicing.
stack[:len(stack)-1]shortens the slice and copies nothing; the value is read first. - Assigning to an element.
stack[len(stack)-1] += ...builds a new string and stores it back, because strings are immutable.
Complexity
Time: proportional to the size of the output, plus the input. Each input character is handled once. The expensive step is strings.Repeat and the string concatenation when a group closes, which copy text whose total length is bounded by the output. Nested groups can copy the same characters at several levels, so the work is O(n + m·d) in the worst case, where m is the output length and d the nesting depth; with at most 30 input characters, d is small.
Space: O(n + m). The stack holds counts and partial outputs, and the longest entry can approach the length of the result.
Edge cases and common mistakes
- Multi-digit counts.
"10[a]"gives tenas. Treating each digit as a separate count would produce 1 and 0; the code appends a digit to the existing count entry instead. - Letters before any bracket. In
"ab2[c]d"the answer is"abccd". The leadingabneeds a buffer, which is why the letter branch creates one when the stack is empty. - Back-to-back groups. In
"2[a]2[b]", after the first group closes, the buffer"aa"sits on the stack. The next digit finds a top that isn't a number, so it starts a new count rather than extending one. The result is"aabb". - Counts directly inside a group. In
"2[3[a]]"the top is an empty buffer when3arrives.Atoi("")fails, so a new count starts, and the answer is sixas. - Digits and letters kept apart. The approach works because the input never has digits inside the text. A digit in the original data would be mistaken for part of a count.
- Treating bytes as characters. This input is ASCII, so bytes and runes agree, but ranging gives runes, which is the safe default.
Testing
"3[a]2[bc]"gives"aaabcbc"."3[a2[c]]"gives"accaccacc"."2[abc]3[cd]ef"gives"abcabccdcdcdef"."10[a]"gives"aaaaaaaaaa"."2[a]2[b]"gives"aabb"."2[2[2[a]]]"gives"aaaaaaaa".