leetcode hot 100-20. 有效的括号

20. 有效的括号

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

思路：HashMap + 栈

使用map存下右括号与左括号的映射，

遍历字符串，把遇到的左括号都压入栈中，

如果遇到右括号，判断栈顶元素是否是对应的左括号，如果不是直接返回fasle，否则说明匹配了，把栈顶的左括号弹出栈，以便下个左括号能出现在栈顶

 1 class Solution {
 2     public boolean isValid(String s) {
 3         // 使用map存下右括号与左括号的映射
 4         HashMap<Character, Character> map = new HashMap<>();
 5         map.put(')', '(');
 6         map.put('}', '{');
 7         map.put(']', '[');
 8         Stack<Character> stack = new Stack<Character>();
 9 
10         // 遍历字符串，把遇到的左括号都压入栈中
11         for(int i = 0; i < s.length(); i++){
12             if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
13                 stack.push(s.charAt(i));
14             }else{
15                 // 如果遇到右括号，判断栈顶元素是否是对应的左括号，如果是则继续遍历，否则直接返回fasle
16                 if(stack.isEmpty() || stack.peek() != map.get(s.charAt(i))){
17                     return false;
18                 }
19                 stack.pop();    // 把栈顶的左括号弹出栈
20             }
21         }
22         return stack.isEmpty();
23     }
24 }

leetcode 执行用时：2 ms > 77.18%, 内存消耗：36.4 MB > 98.25%

复杂度分析：

时间复杂度：O(n). 遍历了一遍字符串，所以时间复杂度为O(n)

空间复杂度：O(n), 空间复杂度主要来源于栈，栈的大小最坏为O(n), 即当字符串全是左括号时，必须将每个字符都入栈。

思路二：只使用栈

遍历字符串，把遇到的左括号把相应的右括号压入栈中，

如果遇到右括号，判断栈顶元素是否是相同的右括号，或者栈为空如果不是直接返回fasle，把栈顶的右括号弹出栈，以便下个右括号能出现在栈顶

 1 class Solution {
 2     public boolean isValid(String s) {
 3         
 4         Stack<Character> stack = new Stack<Character>();
 5 
 6         // 遍历字符串，把遇到的左括号把相应的右括号压入栈中
 7         for(int i = 0; i < s.length(); i++){
 8             if(s.charAt(i) == '('){
 9                 stack.push(')');
10             }else if(s.charAt(i) == '{'){
11                 stack.push('}');
12             }else if(s.charAt(i) == '['){
13                 stack.push(']');
14             }else{
15                 // 如果遇到右括号，判断栈顶元素是否是相同的右括号，或者栈为空，如果是则继续遍历，否则直接返回fasle
16                 if(stack.isEmpty() || stack.peek() !=s.charAt(i)){
17                     return false;
18                 }
19                 stack.pop();
20             }
21         }
22         return stack.isEmpty();
23     }
24 }

leetcode 执行用时：2 ms > 77.18%, 内存消耗：36.1 MB > 99.94%

复杂度分析：

时间复杂度：O(n). 遍历了一遍字符串，所以时间复杂度为O(n)

空间复杂度：O(n), 空间复杂度主要来源于栈，栈的大小最坏为O(n), 即当字符串全是左括号时，必须将每个字符对应的右括号都入栈。