Leetcode problem 20: Valid Parentheses
Question:
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.
Below is one of the solutions:
class Solution {
// Initialize HashMap
static final HashMap<Character, Character> hashMap = new HashMap<>();
static {
hashMap.put(')', '(');
hashMap.put('}', '{');
hashMap.put(']', '[');
}
public boolean isValid(String s) {
// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
// If the current character is a closing bracket
if(hashMap.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 the mapping for this bracket doesn't match the stack's top element, return false;
if(topElement != hashMap.get(c)){
return false;
}
}else{
// If it was an opening bracket, push to the stack.
stack.push(c);
}
}
return stack.isEmpty();
}
}
Let's do the test:
First test case:
Input:
"(()){[()]}"
Output:
true
And another test case:
Input:
"](())"
Output:
false
OK! Let's keep practising.
Top comments (0)