394.decode-string.md

394. Decode String

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Stack

Let's use 30[a20[bc]d]efg as example:

• We iterate all character and determine what the character is.
  • For number digit, we will iterate until we meet [. and push the number, for example 123[, we will parse to be 123 and push 123.
  • For [ or letter, just push into stack.
  • For ], we will pop out until we meet the number in stack, (it might be 123 / [ / abc in stack when meeting ] at that moment) and we will copy that string times (it will be "adb" x 100 times and push back the result into stack.
• Once we finish all strings copy times, we pop out from stack to form the result string.

fun decodeString(s: String): String {
    // x100[a99[bc]y]z
    val stack = Stack<String>()
    var number = 0
    for (c in s) {
        if (c.isDigit()) {
            // We can't call `toInt()` which returns the Ascii code number.
            number = (number * 10) + (c - '0')
        } else if (c == '[') {
            stack.push(number.toString())   // Push the number into stack
            stack.push(c.toString())        // Push the "[" into stack
            // Remember to reset the number
            number = 0
        } else if (c == ']') {
            // 987[abc]
            // Stack = 987, [, a, b, c
            val strList = LinkedList<String>()
            while (stack.isNotEmpty() && stack.peek() != "[") {
                strList.addFirst(stack.pop())
            }
            // Pop out "["
            stack.pop()
            // Pop out the number
            val repeatedTimes = stack.pop().toInt()
            val str = strList.joinToString("").repeat(repeatedTimes)
            stack.push(str)
        } else {
            stack.push(c.toString())
        }
    }
    // Concatenate all the strings in stack
    return stack.joinToString("")
}

• Time Complexity: O(s + S) where s is the length of the encoded string and S is the total length after decoding.
• Space Complexity: O(S) where S is the total length after decoding.

Recursive

TDOO: Add recursive solution.