grid47 Exploring patterns and algorithms
Sep 28, 2024
6 min read
Solution to LeetCode 394: Decode String Problem
You are given a string that is encoded using the pattern k[encoded_string], where the substring inside the square brackets is repeated exactly k times. Your task is to decode the string by expanding it according to the given encoding rule.
Problem
Approach
Steps
Complexity
Input: The input is a string encoded using the pattern k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times.
Example: Input: 2[ab]3[c]
Constraints:
• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[]'.
• All integers in s are in the range [1, 300].
Output: The output is a string representing the decoded version of the input encoded string.
Example: Output: ababc
Constraints:
• The decoded string must follow the encoding rule exactly.
Goal: The goal is to decode the given string by expanding the encoded substrings based on the provided encoding pattern.
Steps:
• Iterate over the input string character by character.
• When encountering a digit, parse the full number to determine how many times to repeat the enclosed substring.
• Recursively process the substring inside the brackets, and concatenate it according to the repetition count.
• Repeat the process until the entire string has been decoded.
Goal: The solution should handle decoding efficiently within the given input size and constraints.
Steps:
• The solution must work for input strings with lengths up to 30 characters.
Assumptions:
• The input string is always valid and well-formed.
• Input: Input: 2[ab]3[c]
• Explanation: The pattern '2[ab]' means 'ab' is repeated 2 times to form 'abab', and '3[c]' means 'c' is repeated 3 times to form 'ccc'. Combining these gives the final output 'ababccc'.
• Input: Input: 2[a2[b]]
• Explanation: First, decode 'a2[b]' where 'b' is repeated 2 times to form 'bb', so 'a2[b]' becomes 'abb'. Repeating this 2 times gives 'abbabb'.
Approach: The approach involves iterating over the string, decoding the substrings inside brackets, and repeating them according to the specified number of repetitions.
Observations:
• The problem involves parsing numbers and substrings, so a stack-based or recursive approach would be effective.
• A recursive approach can work well, where we decode each substring and repeat it according to the number.
Steps:
• Iterate through the string, identifying numbers (which represent the repetition count) and brackets (which define the boundaries of the encoded substrings).
• When encountering a number, extract the full integer value and identify the corresponding substring inside the brackets.
• Use recursion to decode the substring and repeat it the appropriate number of times.
• Concatenate the decoded result and continue until the entire string is processed.
Empty Inputs:
• The input string is guaranteed to have a length of at least 1, so no need to handle empty inputs.
Large Inputs:
• The solution must efficiently handle strings up to 30 characters long.
Special Values:
• Ensure correct handling of nested brackets and repeated substrings.
Constraints:
• The solution must be designed to handle all edge cases, including nested brackets and large numbers for repetitions.
string decodeString(string s) {
int i =0;
return decode(s, i);
}
string decode(string &s, int&i) {
string res ="";
while(i < s.size() && s[i] !=']') {
if(!isdigit(s[i]))
res += s[i++];
else {
int n =0;
while(i < s.size() && isdigit(s[i]))
n = n *10+ (s[i++] -'0');
i++;
string t = decode(s, i);
i++;
while(n-->0) res += t;
}
}
return res;
}
1 : Function Definition
string decodeString(string s) {
Define the main function `decodeString` that takes a string `s` and returns the decoded string.
2 : Variable Initialization
int i =0;
Initialize an integer variable `i` to track the current position in the string `s` during decoding.
3 : Recursive Call
returndecode(s, i);
Call the helper function `decode`, passing the string `s` and the current position `i` as arguments, and return the result.
4 : Function Definition
string decode(string &s, int&i) {
Define the helper function `decode`, which is responsible for decoding the string recursively.
5 : Variable Initialization
string res ="";
Initialize an empty string `res` to accumulate the decoded characters.
6 : While Loop
while(i < s.size() && s[i] !=']') {
Start a `while` loop that processes the string until a closing bracket `]` is encountered.
7 : Character Handling
if(!isdigit(s[i]))
Check if the current character is not a digit (i.e., a literal character that should be added to the result).
8 : Character Addition
res += s[i++];
Add the current character to the result string `res` and increment the position `i`.
9 : Else Block for Number Processing
else {
If the current character is a digit, it indicates the start of a repeat count, so enter the processing block for numbers.
10 : Variable Initialization
int n =0;
Initialize an integer `n` to store the repeat count extracted from the digits in the string.
11 : While Loop for Number Extraction
while(i < s.size() && isdigit(s[i]))
Start a loop to process digits and construct the repeat count `n`.
12 : Number Calculation
n = n *10+ (s[i++] -'0');
Update the repeat count `n` by processing each digit one by one and adjusting the current value of `n`.
13 : Skip Bracket
i++;
Increment `i` to skip the opening bracket `[` after extracting the repeat count.
14 : Recursive Call for Substring
string t = decode(s, i);
Recursively call `decode` to process the substring enclosed in the brackets and get the decoded substring `t`.
15 : Skip Closing Bracket
i++;
Increment `i` to skip the closing bracket `]` after processing the substring.
16 : Repeat and Append
while(n-->0) res += t;
Repeat the decoded substring `t`, `n` times and append it to the result string `res`.
17 : Return Statement
return res;
Return the fully decoded string `res` after all characters and substrings have been processed.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) as each character is processed once during the decoding.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) in the worst case due to recursion and string concatenation.
