20. Valid Parentheses (Easy)
https://leetcode.com/problems/valid-parentheses/
Given a string 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.
Note that an empty string is also considered valid.
Example 1:
Input: "()" Output: true
Example 2:
Input: "()[]{}" Output: true
Example 3:
Input: "(]" Output: false
Example 4:
Input: "([)]" Output: false
Example 5:
Input: "{[]}" Output: true
Solutions
class Solution {
// The key idea is to employ stack to solve this problem.
public boolean isValid(String str) {
if (str == null) {
return true;
}
Set<Character> openP = new HashSet();
openP.add('(');
openP.add('{');
openP.add('<');
openP.add('[');
Set<Character> closeP = new HashSet();
closeP.add(')');
closeP.add('}');
closeP.add('>');
closeP.add(']');
Map<Character, Character> pairs = new HashMap<>();
pairs.put(')', '(');
pairs.put('}', '{');
pairs.put('>', '<');
pairs.put(']', '[');
Stack<Character> stack = new Stack<>();
for (int i = 0, l = str.length(); i < l; i++) {
// must be Object type, rather than primary type
Character c = str.charAt(i);
if (openP.contains(c)) {
stack.push(c);
continue;
}
if (closeP.contains(c)) {
if (stack.size() == 0) {
return false;
}
if (pairs.get(c) != stack.pop()) {
return false;
}
}
}
return stack.isEmpty();
}
}