
Description
The problem requires decoding a string that is encoded in a specific format. The format is such that each group of encoded characters is represented as k[encoded_string]
, where k
is the number of times the encoded_string
should be repeated. The task is to decode the string according to these rules.
Intuition
The problem can be intuitively solved using a stack data structure, which helps to manage nested and sequential decoding processes. The stack stores characters and numbers as we traverse the string. When we encounter a closing bracket (]
), it signals that we have reached the end of an encoded part, and the characters stored in the stack can be processed and decoded accordingly.
Approach
- Stack Utilization: Traverse through each character in the string:
- If the character is not a closing bracket (
]
), push it onto the stack. - When encountering a closing bracket: - Pop characters from the stack until an opening bracket ([
) is found, forming theencoded_string
. - Pop the digits (representingk
) and convert them to an integer. - Repeat theencoded_string
k
times and push the result back onto the stack. - Building the Result: After processing the entire string, the stack will contain the decoded characters in order. Pop elements from the stack to form the final decoded string.
Complexity
Time Complexity:
The time complexity is O(n), where n
is the length of the string. Each character is processed and added to the stack only once.
Space Complexity:
The space complexity is O(n) as we may store all characters in the stack in the worst case.
Code
C++
class Solution {
public:
string decodeString(string s) {
stack st;
for(char ch : s) {
if(ch != ']') {
st.push(ch);
continue;
}
string innerString = "";
while(!st.empty() && st.top() != '[') {
innerString = st.top() + innerString;
st.pop();
}
st.pop(); // Pop '['
string multiplierStr = "";
while(!st.empty() && isdigit(st.top())) {
multiplierStr = st.top() + multiplierStr;
st.pop();
}
int multiplier = stoi(multiplierStr);
string repeatedString = "";
for(int i = 0; i < multiplier; ++i) {
repeatedString += innerString;
}
for(char c : repeatedString) {
st.push(c);
}
}
string result = "";
while(!st.empty()) {
result = st.top() + result;
st.pop();
}
return result;
}
};
Python
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for char in s:
if char != ']':
stack.append(char)
continue
innerString = ""
while stack and stack[-1] != '[':
innerString = stack.pop() + innerString
stack.pop() # Pop '['
multiplier = ""
while stack and stack[-1].isdigit():
multiplier = stack.pop() + multiplier
stack.append(int(multiplier) * innerString)
return ''.join(stack)
Java
class Solution {
public String decodeString(String s) {
Stack stack = new Stack<>();
for(char ch : s.toCharArray()) {
if(ch != ']') {
stack.push(ch);
continue;
}
StringBuilder innerString = new StringBuilder();
while(!stack.isEmpty() && stack.peek() != '[') {
innerString.insert(0, stack.pop());
}
stack.pop(); // Pop '['
StringBuilder multiplierStr = new StringBuilder();
while(!stack.isEmpty() && Character.isDigit(stack.peek())) {
multiplierStr.insert(0, stack.pop());
}
int multiplier = Integer.parseInt(multiplierStr.toString());
String repeatedString = innerString.toString().repeat(multiplier);
for(char c : repeatedString.toCharArray()) {
stack.push(c);
}
}
StringBuilder result = new StringBuilder();
while(!stack.isEmpty()) {
result.insert(0, stack.pop());
}
return result.toString();
}
}
JavaScript
var decodeString = function(s) {
const stack = []
for(const char of s) {
if(char !== "]") {
stack.push(char)
continue
}
let currentChar = stack.pop()
let innerString = ""
while(currentChar !== "[") {
innerString = currentChar + innerString
currentChar = stack.pop()
}
currentChar = stack.pop()
let multiplier = ""
while(!Number.isNaN(Number(currentChar))) {
multiplier = currentChar + multiplier
currentChar = stack.pop()
}
stack.push(currentChar)
stack.push(innerString.repeat(Number(multiplier)))
}
return stack.join('')
};