LeetCode_30_ValidParentheses

1. question: 有效的括号（简单）

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

有效字符串需满足：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

2. answers

这道题也是比较简单的，采用栈来做。遇到左括号，就入栈；遇到右括号，则弹栈，判断两个元素是否匹配。

这里要注意，不匹配有以下三种情况：

1. 遍历完字符串，栈中有多余的元素（左括号多）
2. 在遍历过程中，不匹配（括号不匹配）
3. 在遍历的过程中，遇到右括号，但栈为空（右括号多）

代码如下所示：

public class Solution_0027 {

    public static boolean isValid(String s) {

        // 如果是奇数个字符，则肯定不匹配
        if(s.length() % 2 != 0) {
            return false;
        }

        List<Character> left = new ArrayList<>();
        List<Character> right = new ArrayList<>();

        left.add('(');
        left.add('{');
        left.add('[');

        right.add(')');
        right.add('}');
        right.add(']');

        Stack<Character> stack = new Stack<>();

        char[] chars = s.toCharArray();

        for(char c: chars) {

            // 判断是否是左括号，是的话，就入栈
            if(left.contains(c)) {
                stack.push(c);
            } else {

                // 有括号，开始弹栈匹配
                // 如果栈为空，说明不匹配
                if(stack.isEmpty()) {
                    return false;
                }

                Character pop = stack.pop();

                // 获取当前右括号对应的左括号，判断与栈中的括号是否一致，一致则说明匹配。
                int i = right.indexOf(c);
                Character character = left.get(i);

                if(pop != character) return false;
            }
        }

        // 最后判断栈是否为空，空则表示匹配完，否则没有匹配完。
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println();

//        String s = "()";
//        String s = "(){}[]";
//        String s = "(]";
//        String s = "([)]";
//        String s = "{[]}";
        String s = "}{";
        System.out.println(isValid(s));

    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。