[数据结构与算法]【力扣】难度【简单】20. 有效的括号

标题：20. 有效的括号
难度：简单

描述：

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

有效字符串需满足：

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

示例 1：

输入： s = “()”
输出： true

示例 2：

输入： s = “()[]{}”
输出： true

示例 3：

输入： s = “(]”
输出： false

示例 4：

输入： s = “([)]”
输出： false

示例 5：

输入： s = “{[]}”
输出： true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行结果： 通过
执行用时： 1 ms, 在所有 Java 提交中击败了98.90%的用户
内存消耗： 36.6 MB, 在所有 Java 提交中击败了40.06%的用户
通过测试用例： 91 / 91

题解：

class Solution {
    public boolean isValid(String s) {
        //不是偶数，必然不匹配，直接返回
        if(s.length() % 2 != 0){
            return false;
        }
        //只存左括号字符，如果最后一位匹配，就删除掉最后一位匹配的字符，类似消除游戏
        List list =new ArrayList();
        //创建字典   key记录左括号，value记录右括号
        Map<Character,Character> map = new HashMap();
         map.put('(',')');
         map.put('[',']');
         map.put('{','}');
         //遍历字符串取字符
        for(int i = 0;i < s.length();i++){
            //取字符
            char item = s.charAt(i);
            //如果字符是右括号，就开始判断是否符合规则
            if(item == ')' || item == '}'||item == ']'){
              //从list取出字符获取对应值，和当前字符匹配，不匹配代表不符合规则
              
              int prevIndex = list.size()-1;
             /**
              * list.get(prevIndex)  取最后一个元素
              * map.get(list.get(prevIndex))  取出字典对应的左括号
              * item != map.get(list.get(prevIndex))  如果取出的左括号和当前有括号不匹配
              * 代表不符合规则
              */
              if(prevIndex < 0 || item != map.get(list.get(prevIndex))){
                  return false;
              }else{
                  //如果最后一位匹配  就删除掉list最后一个字符 
                  list.remove(prevIndex);
              }
            }else{
                //如果是左括号就添加进list
                list.add(item);
            }
        }
      return list.size() == 0;
    }
}