20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104-
s仅由括号'()[]{}'组成
- Valid Parentheses
Easy
7344301Add to ListShare
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.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true
Constraints:
1 <= s.length <= 104-
sconsists of parentheses only'()[]{}'.
解题思路：
算法原理
栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
算法流程
如果 c 是左括号，则入栈 push；
否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 false。
class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}
char[] str = s.toCharArray();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < str.length; i++) {
char cha = str[i];
if (cha == '(' || cha == '[' || cha == '{') {//左括号入栈对应的右括号
stack.add(cha == '(' ? ')' : (cha == '[' ? ']' : '}'));
} else {
if (stack.isEmpty()) {
return false;
}
char last = stack.pop();//右括号出栈，和现在的遇到的时候一致，不一致直接返回false
if (cha != last) {
return false;
}
}
}
return stack.isEmpty();
}
}
image-20210428092712773
