LeetCode 394: Decode String

Problem

LeetCode 394: Decode String (Medium)

Problem Statement: Decode a string that has been encoded in a specified format.

In the encoded string, k[str] means decode the string str and repeat the result k times. The input encoding is always valid: k is always a positive integer, there is no extra whitespace, the square brackets match, etc. str may contain more letters, integers and brackets, following the same format rules. However, the decoded string will consist only of lowercase letters (no digits, brackets, or other characters).

Solution

The solution described here is based on this solution by bluedawnstar.

We will implement a recursive function, DecodeString. The solution strategy is to process the input string character by character in one pass, taking different actions based on whether the current character is a digit, a letter, or a closing bracket. Here are the three cases:

Digit

If the character is a digit, we know that this part of the string is an integer followed by an opening bracket, a substring, and a closing bracket. We can process this section using three steps:

• Read all the digits before the opening bracket and interpret them as an integer n. This is the number of times to repeat the string inside the brackets.

• Recursively call DecodeString on the string inside the brackets. That string may contain more digits, letters, and brackets, so there may be further recursive calls.

• Append n copies of the result to the output string.

Letter

Append the letter to the output string.

Closing bracket

A closing bracket means a substring is complete, so return the result.

Pseudocode

for each character c in the input string
    if c is a digit
        convert consecutive digits to an integer n
        recursively call DecodeString
        append n copies of the result to the output string
    else if c is a letter, append it to the output string
    else if c is ']', return the current output string

One implementation detail: It simplifies the recursive function if we store the current input string position as a class-level variable. Since we’re always moving forward in the input string, this means a recursive call can just continue from the current position and doesn’t have to return how many input characters it processed. We can just initialize the position to 0 when the program starts, and increment it whenever we process a character. It doesn’t matter whether we’re in the first call to DecodeString or ten recursive calls deep.

Code

Decode String on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.