leetcode第20题

原链接：https://leetcode-cn.com/problems/valid-parentheses

题目描述

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

有效字符串需满足：

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

示例 1：

输入：s = "()"，输出：true

示例 2：

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

示例 3：

输入：s = "(]"，输出：false

示例 4：

输入：s = "([)]"，输出：false

示例 5：

输入：s = "{[]}"，输出：true

解题思路

解题过程中会用到数据结构：栈

依次遍历给定的字符串s的每个字符，如果当前遍历的字符是 '('，'['，'{' 这三个字符其中之一时，将其入栈，放入栈顶。

如果当前遍历的字符是 ')'，']'，'}' 这三个字符其中之一时，判断栈顶的字符和当前遍历的字符是否满足如下条件：

1. 当前：')'，栈顶'('
2. 当前：']'，栈顶'['
3. 当前：'}'，栈顶'{'

当满足上述三个条件之一，则栈顶字符出栈，继续遍历剩下的字符，如果不满足任何条件，那么就可以返回false了，因为这种情况后面的字符永远也不会与之匹配。

直到遍历完所有的字符。如果此时栈中没有任何字符，则证明能全部闭合。否则不能全部闭合。

代码（java）

class Solution {
    public boolean isValid(String s) {
        if (s==null||s.length()%2!=0){
            return false;
        }
        LinkedList<Character> linkedList=new LinkedList();
        char[] as=s.toCharArray();
        for(char a:as){
            if(a=='{'||a=='['||a=='('){
                linkedList.addLast(a);
            }else{
                if(linkedList.size()>0){
                    char c=linkedList.getLast();
                    if(c=='{'&&a=='}'||c=='('&&a==')'||c=='['&&a==']'){
                        linkedList.removeLast();
                    }else{
                        return false;
                    }
                }else{
                    return false;
                }
            }
        }
        if(linkedList.size()>0){
            return false;
        }
        return true;
    }
}