Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Input: s = "3[a2[c]]"
Output: "accaccacc"
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Array problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: The stack follows the Last In First Out (LIFO) Principle, the top of the stack would have the data we must decode.
1. Start decoding the last traversed string by popping the string decodedString and number k from the top of the stack.
2. Pop from the stack while the next character is not an opening bracket [ and append each character (a-z) to the decodedString.
3. Pop opening bracket [ from the stack.
4. Pop from the stack while the next character is a digit (0-9) and build the number k.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def decodeString(self, s: str) -> str:
stack = []
cur_level = []
num = 0
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char.isalpha():
cur_level.append(char)
elif char == '[':
stack.append((num, [*cur_level]))
cur_level = []
num = 0
elif char == ']':
prev_level_num, prev_level = stack.pop()
cur_level_string = "".join(cur_level)
cur_level = [*prev_level, prev_level_num * cur_level_string]
return "".join(cur_level)
class Solution {
public String decodeString(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ']') {
List<Character> decodedString = new ArrayList<>();
// get the encoded string
while (stack.peek() != '[') {
decodedString.add(stack.pop());
}
// pop [ from the stack
stack.pop();
int base = 1;
int k = 0;
// get the number k
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
k = k + (stack.pop() - '0') * base;
base *= 10;
}
// decode k[decodedString], by pushing decodedString k times into stack
while (k != 0) {
for (int j = decodedString.size() - 1; j >= 0; j--) {
stack.push(decodedString.get(j));
}
k--;
}
}
// push the current character to stack
else {
stack.push(s.charAt(i));
}
}
// get the result from stack
char[] result = new char[stack.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return new String(result);
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the length of output
O(N)
since we basically traverse the string and do constant operation on each characterO(N)
for the worst case, as the recursion stack can be at most O(n). Think about what the maximum number of pairs of parenthesis could be in a string of size n.