20. Valid Parentheses
Given a string containing just the characters
An input string is valid if:
'(', ')', '{', '}', '[' 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
思路：给定一个只包含字符’（’，’）’，'{‘，’}’，'[‘和’]’的字符串，确定输入字符串是否有效。必须使用相同类型的括号关闭左括号。必须以正确的顺序关闭打开括号。
用一个栈，我们开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，若此时栈为空，则直接返回false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回false。
代码如下：
public class ValidParentheses {
public boolean isValid(String s) {
Stack<Character> temp = new Stack<>();
char[] chars = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (chars[i] == '(' || chars[i] == '{' || chars[i] == '[') {
temp.push(chars[i]);
} else {
if (temp.empty()) return false;
if (chars[i] == ')' && temp.peek() != '(') return false;
if (chars[i] == '}' && temp.peek() != '{') return false;
if (chars[i] == ']' && temp.peek() != '[') return false;
temp.pop();
}
}
return temp.empty();
}
}