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: "()[]{}"
Output: true
Input: "(]"
Output: false
EDGE CASE
Input: "("
Output: false
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 brackets problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use Stack to store brackets and check if open and close bracket matching with each other or not.
1. Create a Stack which will store the brackets.
2. Process each bracket of the expression one at a time.
3. If encounter a closing bracket, then check the element on top of the stack. If the element at the top of the stack is an opening bracket of the same type, then pop it off the stack and continue processing. Else, this implies an invalid expression.
4. If encounter an opening bracket, push it onto the stack.
5. In the end, if we are left with a stack still having elements, then this implies an invalid expression.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def isValid(self, s):
if s == "":
return True
# Create a Stack which will store the brackets.
stack = [s[0]]
# Process each bracket of the expression one at a time.
for i in range(1,len(s)):
# If encounter a closing bracket, then check the element on top of the stack.
if s[i] == ')':
# If the element at the top of the stack is an opening bracket of the same type, then pop it off the stack and continue processing. Else, this implies an invalid expression.
if stack and stack[-1] == '(':
stack.pop()
else:
return False
elif s[i] == ']':
if stack and stack[-1] == '[':
stack.pop()
else:
return False
elif s[i] == '}':
if stack and stack[-1] == '{':
stack.pop()
else:
return False
else:
# If encounter an opening bracket, push it onto the stack.
stack.append(s[i])
# In the end, if we are left with a stack still having elements, then this implies an invalid expression.
return not stack
class Solution {
public boolean isValid(String s) {
// Hash table that takes care of the mappings between open brackets and close brackets
HashMap<Character, Character> mappings = new HashMap<Character, Character>();
mappings.put(')', '(');
mappings.put('}', '{');
mappings.put(']', '[');
// 1. Create a Stack which will store the brackets.
Stack<Character> stack = new Stack<Character>();
// 2. Process each bracket of the expression one at a time.
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 3. If encounter a closing bracket, then check the element on top of the stack.
// If the element at the top of the stack is an opening bracket of the same type,
// then pop it off the stack and continue processing. Else, this implies an invalid expression.
if (mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#'
char topElement = stack.empty() ? '#' : stack.pop();
if (topElement != mappings.get(c)) {
return false;
}
} else {
// 4. If encounter an opening bracket, push it onto the stack.
stack.push(c);
}
// 5. In the end, if we are left with a stack still having elements, then this implies an invalid expression.
return stack.isEmpty();
}
}
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 number of items in the string
O(N)
because we may need to traverse all items in the stringO(N)
because we may need to store all items in the array into a stack