20. Valid Parentheses
Tags: ‘String’, ‘Stack’
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
Solution 1
Use a stack to trace left parentheses
public boolean isValid(String s) {
Map<Character, Character> mappings = new HashMap<Character, Character>();
mappings.put(')', '(');
mappings.put('}', '{');
mappings.put(']', '[');
if (s == null || s.length() == 0) return true;
if (s.length() % 2 != 0) return false;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (mappings.containsKey(c)) {
char top = stack.isEmpty() ? '#' : stack.pop();
if (top != mappings.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}