Dare2Solve
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.
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.
Stack Utilization: Traverse through each character in the string:
]
), push it onto the stack.[
) is found, forming the encoded_string
.k
) and convert them to an integer.encoded_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.
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.
The space complexity is O(n) as we may store all characters in the stack in the worst case.
class Solution {
public:
string decodeString(string s) {
stack<char> 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;
}
};
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)
class Solution {
public String decodeString(String s) {
Stack<Character> 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();
}
}
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('')
};