leetCode 020 有效括号

题目描述：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例输入输出：

输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
输入：s = "([)]"
输出：false
输入：s = "{[]}"
输出：true

思路：

用栈和hashMap辅助遍历字符串

• 遍历字符串。遇到非括号直接返回false。遇到左半部分压入栈中，遇到右半部分就与栈顶元素匹配，不匹配直接false，否则弹出栈顶，遍历下一个。到最后如果为空，返回true，否则false。

• 参数：

  • 无

• 终止条件：

  • s.charAt(s.length())，即遍历到字符串的最后一个元素。

• 迭代过程中做的事：

  • 判断此元素是否为左半部分，如果是压入栈

  • 判断此元素是否为右半部分

    • 如果是，当栈非空时与栈顶元素匹配（栈为空直接返回false），匹配成功，弹出栈顶，否则返回false。
    • 不是，直接返回false。

• 复杂度分析：

  • 时间复杂度：只需要遍历一遍，O（n）
  • 空间复杂度：需要额外的空间，最坏情况下全部都是左半部分，O（n）

• 代码：

• class Solution {
    public boolean isValid(String s) {
        //字符串长度为奇，括号不可能完全匹配
        if(s == null || s.length()%2 == 1){
            return false;
        }
  
        //存入括号对
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
  
        Stack<Character> stack = new Stack<>();
  
        for(int i = 0; i < s.length(); i++){
            char temp = s.charAt(i);
  
            if(map.containsKey(temp)){
                //是左半部分括号，压入栈
                stack.push(temp);
            }else if(temp == '}' || temp == ')'|| temp ==']'){
                //是右半部分括号，匹配
                if(stack.isEmpty()){
                    //栈为空，又有右半部分需要匹配的括号，直接返回false
                    return false;
                }
                if(temp == map.get(stack.pop())){
                    //匹配成功，遍历下一个
                    continue;
                }else{
                    //匹配失败，返回false
                    return false;
                }
            }else{
                //该字符既不是左半部分又不是右半部分，返回false
                return false;
            }
        }
  
        //匹配到最后，如果栈为空，返回true，否则就是还有括号没被匹配，返回false
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
  }