394.decode-string.md

394. Decode String

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 == '[') {
            // Push the current state into stack (save context)
            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 == ']') {
            // Pop previous state (restore context)
            // 987[abc]
            // Stack = 987, [, a, b, c
            val strList = ArrayDeque<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("")
}

There is another approach to use "two stacks" to solve the problem. One stack is for the number, one stack is for the string. We save context by pushing the number and string into the stack when we see [ and pop them out when we see ]. Idea is the same.

• 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

There are some key questions to ask when solving the problem recursively:

1. What's the possible input:
   • A basic string like "abc".
   • A string pattern k[encoded_string] like "3[...]" or nested pattern "3[a2[c]]".
   • A string pattern k[encoded_string] with multiple occurrences, like "2[ab]3[cd]ef".
2. What are the "tokens" to parse?
   • Digits (it might be multi-digit)
   • Letters
   • Opening bracket [
   • Closing bracket ]
3. When should we recurse?
   • When seeing [? Or after seeing ]? Or before seeing ]?
   • When seeing ], we can recurse to parse the content inside [].
4. What's the unit of work?
   • Decode characters until we meet ] or the end of the string.

The pattern k[...] can be decoded recursively. The content inside [...] has the same structure as the entire problem.

"3[a2[c]]"
    ↓
    "a2[c]" ← This is another encoded string! Same format as the input!
    ↓
    "c" ← Base case: just a letter

// Recursive thinking:
decode("3[a2[c]]") 
    = repeat(3, decode("a2[c]"))
                ^^^^^^^^^^^^^^^ 
                ↑
                This is a recursive call!

When we see [:

• We need to decode what's inside.
• Inside might have more [...] nested. → Recursive call.
• Keep decoding until we meet ].

When we meet ]:

• We're done with this level.
• Return the decoded string.

Let's trace "3[a2[c]]" step by step:

Call stack visualization:

  decode(s, index=0)
  ├─ Read '3' → number = 3
  ├─ See '[' at index=1
  │  ├─ index = 2
  │  ├─ RECURSE: decode(s, index=2)  ← Start of nested call
  │  │  ├─ Read 'a' → result = "a"
  │  │  ├─ Read '2' → number = 2
  │  │  ├─ See '[' at index=4
  │  │  │  ├─ index = 5
  │  │  │  ├─ RECURSE: decode(s, index=5)  ← Deeper nesting
  │  │  │  │  ├─ Read 'c' → result = "c"
  │  │  │  │  ├─ See ']' at index=6
  │  │  │  │  └─ RETURN "c" (index now = 7)
  │  │  │  ├─ nested = "c"
  │  │  │  ├─ result = "a" + "c" * 2 = "a" + "cc" = "acc"
  │  │  │  ├─ See ']' at index=7
  │  │  │  └─ RETURN "acc" (index now = 8)
  │  ├─ nested = "acc"
  │  ├─ result = "" + "acc" * 3 = "accaccacc"
  │  └─ index = 8 (end of string)
  └─ RETURN "accaccacc"

Final result: "accaccacc"

private var i = 0

fun decodeString(s: String): String {
    val n = s.length
    var num = 0
    val str = StringBuilder()
    while (i < n) {
        val c = s[i]
        when {
            // 1. Build the multiplier
            c.isDigit() -> {
                num = num * 10 + (c - '0')
                i++
            }
            // 2. Dive: The unit of work is everything inside `[...]`.
            c == '[' -> {
                i++ // Skip `[`
                val nestedStr = decodeString(s)
                repeat(num) {
                    str.append(nestedStr)
                }
                // Remember to reset the number for the next nested string.
                num = 0
            }
            // 3. Return: This unit of work is finished
            c == ']' -> {
                i++ // Skip `]`
                // Hits the end of the nested string, we returns the current result to the caller.
                return str.toString()
            }
            // 4. Base Case: Just a character
            else -> {
                str.append(c)
                i++
            }
        }
    }

    // Or hits the end of the string, it might not nested, like "abc", we just return the result.
    return str.toString()
}

• 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(D + S) where D is the depth of the nested string and S is the total length after decoding.