Question
Formatted question description: https://leetcode.ca/all/20.html
20 Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
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
@tag-stack
Algorithm
Here you need to use a stack to start traversing the input string. If the current character is the left half bracket, it will be pushed onto the stack. If the right half bracket is encountered, if the stack is empty at this time, it will directly return false, such as If it is not empty, remove the top element of the stack, if it is the corresponding left half bracket, continue to loop, otherwise return false.
Pitfalls
- After the final for is over, it depends on whether the stack is empty or not, if it is all “((((((“)
- When popping, did not check if the stack is empty
Code
Java
import java.util.Stack;
public class Valid_Parentheses {
public class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) return false;
Stack<Character> sk = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') sk.push(c);
else if (c == ')' || c == '}' || c == ']') {
// @note: I missed stack check
if (sk.isEmpty()) return false;
char pop = sk.pop();
if (!valid(pop, c)) return false;
}
else return false; // some other chars except parenthesis
}
// @note: i missed sanity check, what if only "["
return sk.isEmpty() ? true : false;
}
public boolean valid(char left, char right) {
return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}
}
}