Decode String Introduction
Decode String Introduction
Decode String is a problem where a string of numbers and letters need to be decoded to reveal a hidden message. This is a common, albeit simplified, problem in cryptography, involving a multi-step approach and the application of recursion and additional data structures to improve time complexity.
Decode String Problem
Decode String Problem
Part 1 - Decode String Simplified
The simplified version of "decode string" presents us with an alpha-numeric string where a number may come before any letter. Given such a string, decode the string so that each number/letter combinations is expanded.
Example 1
input: 4a
output: aaaa
Example 2
input: a2b10c
output: abbcccccccccc
Part 2 - Decode String (Standard Version)
Given an encoded string s, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer.
Constraints
1 <= s.length <= 30sconsists of lowercase English letters, digits, and square brackets[].sis guaranteed to be a valid input.- All the integers in
sare in the range[1, 300].
Example 1
input: abcdefg
output: abcdefg
Example 2
input: ab2[c]3[de4[f]]
output: abccdeffffdeffffdeffff
Example 3
input: 2[2[2[a]]]
output: aaaaaaaa
Decode String Solutions
Decode String Solutions
There are two problems we will need to solve to successfully expand our string:
-
Parsing - We need to be able to walk through our input string and extract the counts and groupings.
-
Groups within groups - We need a way of tracking the nested structure of our encoded string.
The second issue is certainly related to parsing, but we will pull in some additional tools to manage it.
We will start with the simplified problem as a warmup exercise. This will give us a chance to get a feel for how parsing works. Once we have that under our belt we will move on to the more complex Leetcode version.
Approach to Simplified Problem
As a reminder, in this case, we have an alpha-numeric string where an integer may come before any alpha character. To solve this problem we will walk through our string one character at a time. We will use a string variable called count to store any digit information we encounter. We are using a string because we may need to store multiple digits and concatenating strings is trivial. Now each time we encounter an alpha character we can look at the count to determine the number of times that character should appear. After adding an alpha character, count will be reset.
In the python solution, we are using a bit of cleverness when it comes to multiplying count by char. Multiplying an integer N by a string S duplicates the string N times. In the javascript solution, we need to create a helper function to determine if a character is a digit.
Decode String Python, JavaScript and Java Solutions - Simplified Version
def decode_string(s: str) -> str:
solution_str = ""
# using a string to make our lives easier
count = ""
for char in s:
if char.isDigit():
count += char
else:
if count == "":
solution_str += char
else:
# multiplying a string by an int creates copies of the string!
solution_str += int(count) * char
count = ""
return solution_str1def decode_string(s: str) -> str:
2 solution_str = ""
3
4 # using a string to make our lives easier
5 count = ""
6
7 for char in s:
8 if char.isDigit():
9 count += char
10 else:
11 if count == "":
12 solution_str += char
13 else:
14 # multiplying a string by an int creates copies of the string!
15 solution_str += int(count) * char
16 count = ""
17
18 return solution_strTime/Space Complexity
- Time complexity:
O(n), as we are iterating through our input string once and only applyingO(1)operations throughout. - Space complexity:
O(10<sup>n</sup>). The space complexity is a little harder to compute. For instance think about9999a(which we can think of as(10<sup>4</sup>-1)a). We can see that the output string can quickly blow up in size. Because of this our worst-case space isO(10<sup>n</sup>).
Approach to Decode String - Standard Version (Recursion)
Now that we've warmed up using the simpler problem, let's tackle the more difficult problem!
In this more complex version our input string is different in two ways:
-
Now instead of using numbers to expand out a single character, a group of characters may be expanded out. Groups are defined by square brackets
[]. For instance3[ab]would expand out toababab. Note, any time there is a number, it is guaranteed to be followed by[]. -
We are allowed to have groups inside of groups.
Similar to the previous solution we need to walk through our input string and categorize each character. Because we may have groups within groups, as we walk through our string we need a way of tracking which group we are currently parsing. We will introduce a new variable called depth to track this. When we first start parsing the string, depth will be 0. Each time we step into a new group (when we encounter a [) depth will go up by one, and depth will go down by one each time we step out of a group (when we encounter a ]). When depth returns to 0 we will know that we have processed an entire group at the top level.
Our parser will track count like before and store the contents of a group in a new variable called contents. We will employ a clever trick to process each group. We can feed the contents of a group back into our original function to expand out any subgroups! This technique is called recursion.
The Danger of Recursion
A small detail we have glossed over here is the danger of recursion. If we have enough groups within groups, our recursive calls can overwhelm the call stack causing our script to crash! We will address this in our next approach.
Decode String Python, JavaScript and Java Solutions - Standard Version (Recursion)
def decode_string(s: str) -> str:
return_string = ""
count = ""
contents = ""
depth = 0
for char in s:
if depth == 0:
if char.isdigit():
count += char
elif char == "[":
depth += 1
else:
return_string += char
else:
if char == "]":
depth -= 1
if depth == 0:
# we found the end of a grouping
# expand it and add it to our output string.
return_string += int(count) * self.decode_string(contents)
count = ""
contents = ""
else:
contents += char
else:
if char == "[":
depth += 1
contents += char
return return_string1def decode_string(s: str) -> str:
2 return_string = ""
3 count = ""
4 contents = ""
5 depth = 0
6
7 for char in s:
8 if depth == 0:
9 if char.isdigit():
10 count += char
11 elif char == "[":
12 depth += 1
13 else:
14 return_string += char
15 else:
16 if char == "]":
17 depth -= 1
18
19 if depth == 0:
20 # we found the end of a grouping
21 # expand it and add it to our output string.
22 return_string += int(count) * self.decode_string(contents)
23 count = ""
24 contents = ""
25 else:
26 contents += char
27 else:
28 if char == "[":
29 depth += 1
30
31 contents += char
32
33 return return_stringTime/Space Complexity
- Time complexity:
O(n<sup>2</sup>)due to our recursive calls. - Space complexity:
O(10<sup>n</sup>)
Approach to Decode String (Standard Version) (Stacks)
Now, our recursive solution has the weakness of needing to parse subgroups multiple times. For instance take the string 4[3[abc]3[xyz]]. Our parser would walk over the entire string, then over 3[abc]3[xyz], then [abc], and finally over [xyz]. This unnecessarily increases our time complexity!
In this approach, we are going to work on shaving some time off by processing groups as we parse. To do this we are going to create a stack. Each element of the stack represents a group. We will add elements to the stack as we encounter subgroups. Each time we finish parsing a group (encounter a ]) we will pop it off the stack, expand it out, and add it to the new top element on the stack. Once all groups have been processed we will have only a single group in our stack. This is our final solution!
It's worth mentioning that this approach is very similar to the previous approach. The big differences are instead of a call stack, we have a stack of groups and we are cutting down on the number of passes we make in each group to 1.
For our python solution, we are using a simple class called Encoding. A list would have worked just as well, this just keeps the syntax nice. In Javascript, we use an object to serve the same purpose.
Decode String Python, JavaScript and Java Solutions - Standard Version (Stacks)
class Encoding:
def __init__(self, count:str = "", contents:str = "") -> None:
self.count = count
self.contents = contents
def decode_string(s: str) -> str:
encoding_stack = [Encoding()]
count = ""
for char in s:
if char.isdigit():
count += char
elif char == "[":
encoding_stack.append(Encoding(count=count, contents=""))
count = ""
elif char == "]":
encoding = encoding_stack.pop()
expanded_encoding = int(encoding.count) * encoding.contents
encoding_stack[-1].contents += expanded_encoding
else:
encoding_stack[-1].contents += char
return encoding_stack[0].contents1class Encoding:
2 def __init__(self, count:str = "", contents:str = "") -> None:
3 self.count = count
4 self.contents = contents
5
6def decode_string(s: str) -> str:
7 encoding_stack = [Encoding()]
8 count = ""
9
10 for char in s:
11 if char.isdigit():
12 count += char
13 elif char == "[":
14 encoding_stack.append(Encoding(count=count, contents=""))
15 count = ""
16 elif char == "]":
17 encoding = encoding_stack.pop()
18 expanded_encoding = int(encoding.count) * encoding.contents
19 encoding_stack[-1].contents += expanded_encoding
20 else:
21 encoding_stack[-1].contents += char
22
23 return encoding_stack[0].contentsTime/Space Complexity
- Time complexity:
O(n). The time complexity for this is much nicer than the previous solution. We are parsing our input string a single time and doingO(1)operations throughout. - Space complexity:
O(10<sup>n</sup>)
Practice the Decode String Problem With Our AI Interviewer
Practice the Decode String Problem With Our AI Interviewer
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
