Leetcode Problem: Valid Parentheses
Objective:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Pattern: Stack
Approach:
- Use a hashmap to store the paired brackets: key = closed bracket and value = open bracket.
- If the hash map does not contain current character then it is an open bracket. Use a stack to store the open brackets.
- Check if the stack is empty this prevents closing brackets to be added first, in this case it is not valid.
- Check the top of the stack by popping it and if top character is not matched with closing bracket in hashmap then return false.
- If stack is empty then return true because it is a valid parentheses.
- If stack is not empty then return false.
Big-O Notation:
Time Complexity: O(n)
We have iterate n times for each character in the string.
Space Complexity: O(n)
We use a hash map data structures for storage.
Code:
class Solution {
public boolean isValid(String s) {
// use stack to store opening brackets
Stack <Character> stack = new Stack<>();
// use a hashmap to store pairs
Map <Character, Character> hashMap = new HashMap<>();
hashMap.put(')','(');
hashMap.put('}','{');
hashMap.put(']','[');
// iterate through s
// add open brackets to the stack
// if stack is empty or top char is not a match to c
// return false
for(char c : s.toCharArray()){
if(!hashMap.containsKey(c)){
stack.push(c);
} else if(stack.isEmpty() || stack.pop() != hashMap.get(c)){
return false;
}
}
return stack.isEmpty();
}
}
Top comments (0)