You are given an encoded string where k[text] means text repeated exactly k times, and such patterns can be nested. Return the decoded string. The input is always well formed, k is a positive integer, and digits only appear as repeat counts (plain text never contains digits).
2[c] becomes cc, so the outer part is 3[acc].- 1 <= s.length <= 30
- `s` has lowercase letters, digits and square brackets
- 1 <= k <= 300
- The output length is at most 10^5
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force repeatedly searches for an innermost k[text] (one with no brackets inside), replaces it with the expanded text and starts over. It works but rescans the string many times. A stack lets us do it in one pass: when a [ opens, we save the string built so far and the repeat count, and begin building the inner string. When the matching ] closes, the inner string is complete, so we repeat it and append it to the saved outer string. Numbers can have several digits, so build them digit by digit.
Algorithm
- Keep
cur(string being built),num(count being read) and a stack of(prevString, count)pairs. - Digit:
num = num * 10 + digit. [: push(cur, num), then resetcurto empty andnumto 0.]: pop(prev, k)and setcur = prev + cur repeated k times.- Letter: append it to
cur. At the end returncur.
O(output length)Space: O(output length)"10[a]" must give ten letters. In Java use StringBuilder for cur, since repeated string concatenation in a loop is quadratic.class Solution: def decodeString(self, s: str) -> str: stack = [] # (outer string, repeat count) cur, num = '', 0 for c in s: if c.isdigit(): num = num * 10 + int(c) # counts can have many digits elif c == '[': stack.append((cur, num)) # save the outer string cur, num = '', 0 elif c == ']': prev, k = stack.pop() cur = prev + cur * k else: cur += c return cur