leetcode之有效括号

leetcode • Sep 10, 2019

题目描述

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true
示例 2:

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

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

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

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

题解

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;


class Solution {
    public boolean isValid(String s){

        Stack<Character> stack = new Stack<>();
        Set<Character> terminateSet = new HashSet();
        terminateSet.add(')');
        terminateSet.add(']');
        terminateSet.add('}');

        if (s.trim().equals("")){
            return true;
        }

        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);

            if (terminateSet.contains(tmp)){
                if (stack.isEmpty()){
                    return false;
                }
                
                Character pop = stack.pop();
                boolean pair = isPair(tmp, pop);

                if (!pair){
                    return false;
                }
            } else {
                stack.push(tmp);
            }
        }

        return stack.isEmpty();

    }

    public boolean isPair(char terminate, char start){
        if (terminate == ')' && start == '(' ){
            return true;
        } else if (terminate == ']' && start == '['){
            return true;
        } else return terminate == '}' && start == '{';
    }
}

思路

题目应该是来自是编译器的一个小功能，判断括号是否配对。大学的时候上c语言课程的时候思考过这个问题，如果纯手工写会比较麻烦。后面学习了栈数据结构写起来就很容易了。
主要思想就是将未配对的压入栈中，我们可以将右括号叫终结符号，遇到终结符号就弹出一个栈元素，查看他们是否配对，如果配对，继续。如果不配对，那么字符串就不是有效字符串。最后的时候查看栈内元素是否为null，判断这个字符串是否完全匹配了即可。因为null字符也是有效字符串，所以要在开始进行判断。