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).
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:
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.
DecodeStringon the string inside the brackets. That string may contain more digits, letters, and brackets, so there may be further recursive calls.
ncopies of the result to the output string.
Append the letter to the output string.
A closing bracket means a substring is complete, so return the result.
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.
LeetCode Model Solutions
I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.