力扣 有效的括号

括号匹配问题，找到符合的进行抵消。

题目

从题可以看出是嵌套的括号先匹配先做抵消，类似就近原则，这也是栈的典型例题。可以通过枚举多种不同的情况慢慢用if与else做返回。

时间复杂度：O(n)，其中 n 是字符串的长度。空间复杂度：O(n)，主要来自栈的空间。

class Solution {
   public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] charArray = s.toCharArray();

        for (char ch : charArray) {
            //如果是左括号则直接入栈
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
               //如果是右括号，并且此时栈不为空
                if (!stack.isEmpty()) {
                    if (ch == ')') {
                        if (stack.pop() != '(')
                            return false;
                    } else if (ch == '}') {
                        if (stack.pop() != '{')
                            return false;
                    } else {
                        if (stack.pop() != '[')
                            return false;
                    }
                }
                else{ 
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

通过遍历字符串的字符，把左括号入栈，后面加进的在栈顶，再对右括号出栈看是否能够匹配，不匹配就说明无效，最后还要对栈判空，有可能最后栈还有括号说明有多的没有匹配到也是不符合的。当然，也可以写简洁一些。

class Solution {
    public boolean isValid(String s) {
        if(s.isEmpty())
            return true;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.isEmpty()||c!=stack.pop())
                return false;
        }
        return stack.isEmpty();
    }
}

 

原文地址：https://blog.csdn.net/visitorcsdn/article/details/145249997

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！