LeetCode 394 Decode String - Implementation

Two stacks: counts and strings. Push on [, pop and repeat on ].

function decodeString(s): countStack = [] stringStack = [] currString = "" currNum = 0 for char in s: if char.isdigit(): currNum = currNum * 10 + int(char) elif char == '[': countStack.push(currNum) stringStack.push(currString) currString = "" currNum = 0 elif char == ']': count = countStack.pop() prevString = stringStack.pop() currString = prevString + currString * count else: currString += char return currString

$O(n)$ time, $O(m)$ space for stack depth.