讨论/《初级算法》 - 有效的括号/
《初级算法》 - 有效的括号
共 18 个回复

要判断括号的有效性,左括号必须和右括号相对应。如果是有效括号,并且他们中间还有括号,那么他们必须也是有效的,所以最简单的一种方式就是使用栈来解决。


我们遍历字符串中的所有字符

1,如果遇到了左括号,就把对应的右括号压栈(比如遇到了字符'(',就把字符')'压栈)。

2,如果遇到了右括号

  • 1)查看栈是否为空,如果为空,说明不能构成有效的括号,直接返回false。

  • 2)如果栈不为空,栈顶元素出栈,然后判断出栈的这个元素是否等于这个右括号,如果不等于,说明不匹配,直接返回false。如果匹配,就继续判断字符串的下一个字符。


3,最后如果栈为空,说明是完全匹配,是有效的括号,否则如果栈不为空,说明不完全匹配,不是有效的括号。


这里随便举个例子比如字符串是“{([]())}”,画个图来看一下。

image.png

image.png

代码如下

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    //遍历所有的元素
    for (char c : chars) {
        //如果是左括号,就把他们对应的右括号压栈
        if (c == '(') {
            stack.push(')');
        } else if (c == '{') {
            stack.push('}');
        } else if (c == '[') {
            stack.push(']');
        } else if (stack.isEmpty() || stack.pop() != c) {
            //否则就只能是右括号。
            //1,如果栈为空,说明括号无法匹配。
            //2,如果栈不为空,栈顶元素就要出栈,和这个右括号比较。
            //如果栈顶元素不等于这个右括号,说明无法匹配,
            //直接返回false。
            return false;
        }
    }
    //最后如果栈为空,说明完全匹配,是有效的括号。
    //否则不完全匹配,就不是有效的括号
    return stack.isEmpty();
}

看一下运行结果

image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

8
class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        dic={')':'(',']':'[','}':'{'}
        for i in s:
            if i in dic and  stack and stack[-1]==dic[i]:
                stack.pop()
            else:
                stack.append(i)
        return True if len(stack)==0 else False
1
class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0 ){
            return false;
        }
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        Stack<Character> left = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 左括号入栈
            if(map.containsKey(c)){
                left.push(c);
                continue;
            }
            // 右括号出栈进行比较,不相等 或栈为空,直接返回false
            if(map.containsValue(c)){
                if(left.isEmpty() || map.get(left.pop()) != c){
                    return false;
                }
                continue;
            }
            // 如果既不是左括号,又不是右括号,返回false
            return false;
        }
        // 如果最后栈没被清空,返回false
        return left.isEmpty();
    }
}
1
class Solution {
    public boolean isValid(String s) {
        if(s == null || s.length() < 2 ||s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> st = new Stack<>();
        char[] ch = s.toCharArray();
        int len = ch.length;
        int i = 0;
        while(i < len) {
            if(!st.isEmpty() && ((st.peek() == '(' && ch[i] == ')') 
                    || (st.peek() == '[' && ch[i] == ']') 
                    || (st.peek() == '{' && ch[i] == '}'))) {
                st.pop();
            }else {
                st.push(ch[i]);
            }
            i++;
        }
        if(st.isEmpty()) {
            return true;
        }else {
            return false;
        }
    }
}

使用栈就行了
image.png

利用栈解决括号匹配问题

#include<stack>
class Solution {
public:
    bool isValid(string s) {
        int len = s.size();
        if (len <= 1) return false;
        stack<char> stack1;
        for (int i = 0; i < s.size(); ++i) {
            if (stack1.empty()) {
                stack1.push(s[i]);
            } else {
                bool is_match = isMatch(stack1.top(), s[i]);
                if (is_match) {
                    stack1.pop();
                } else {
                    stack1.push(s[i]);
                }
            }
        }
        return stack1.empty() ? true : false;
    }

    bool isMatch(char c1, char c2) {
        if (c1 == '(' && c2 == ')') return true;
        else if (c1 == '[' && c2 == ']') return true;
        else if (c1 == '{' && c2 == '}') return true;
        else return false;
    }
};

做了20多道终于有一道完全没看答案做出来还比较符合标准答案的了,我太难了。

class Solution {
public:
    bool isValid(string s) {
        if (s.size()%2)
            return false;
        stack<char> brackets;
        for (int i = 0; i < s.size(); ++i) {
            if (brackets.size() == 0) {
                if (s[i] == '}' || s[i] == ']' || s[i] == ')')
                    return false;
                else {
                    brackets.push(s[i]);
                    continue;
                }
            }
            if (s[i] == ')') {
                if (brackets.top() != '(')
                    return false;
                else
                    brackets.pop();
            }
            else if (s[i] == ']') {
                if (brackets.top() != '[')
                    return false;
                else
                    brackets.pop();
            }
            else if (s[i] == '}') {
                if (brackets.top() != '{')
                    return false;
                else
                    brackets.pop();
            }
            else
                brackets.push(s[i]);
        }
        if (brackets.size() == 0)
            return true;
        else
            return false;
    }
};
    bool isValid(string s) {
        stack<char> stk;
        for(auto ch : s){
            if(ch == '(') stk.push(')');
            else if(ch == '[') stk.push(']');
            else if (ch == '{') stk.push('}');
            else{
                if(stk.empty() || stk.top() != ch) return false;
                else stk.pop();
            }
        }
        return stk.empty();
    }

思路很简单,分为两种情况:左括号和右括号
左括号就入栈,右括号就要分情况讨论
因为右括号要pop(),所以得先对栈判空。之后再检测当前字符和栈顶字符是否相同
结束循环的return借鉴了高赞,是我年轻开始时没想到,这样的简洁才是代码的美

class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0){return false;}

        Stack<Character> stack = new Stack<>();
        
        //左括号就入栈
        //右括号就先判空,非空再判等之后再出栈
        //检测栈空,空则true;
        for(int i=0 ; i<s.length() ; i++){
            if(s.charAt(i) == '('){stack.push(')');}
            else if(s.charAt(i) == '['){stack.push(']');}
            else if(s.charAt(i) == '{'){stack.push('}');}
            else{
                if(stack.isEmpty()){return false;}
                else{
                    if(s.charAt(i) == stack.peek()){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
        }

        return stack.isEmpty();
    }
}

简单栈应用

class Solution {
public:
    bool isValid(string s) {
        stack<char> mystack={};
        int size=s.size();
        if(size==0) return true;
        for(int i=0;i<size;i++)
        {
            if(mystack.empty()||!isCouple(mystack.top(),s[i]))
            {
                mystack.push(s[i]);
            }
            else
            {
                mystack.pop();
            }
            
        }
        return mystack.empty();
    }
    bool isCouple(char a,char b)
    {
        if(a=='('&&b==')'||
            a=='['&&b==']'||
            a=='{'&&b=='}')
        {
            return true;
        }
        else return false;
    }
};

image.png

递归法

class Solution {
    public boolean isValid(String s) {
        if(s == null || s.length() == 0){
            return true;
        }
        if(s.length()%2 != 0){
            return false;
        }
        int l = -1,r = 10001;
        for(int i = 1;i<s.length();i++){
            if(s.charAt(i) == getCh(s.charAt(i-1))){
                l = i-2;
                r = i+1;
                break;
            }
        }
        if(r == 10001){
            return false;
        }
        while(l >= 0 && r < s.length()){
            if(s.charAt(r) != getCh(s.charAt(l))){
                break;
            }
            l--;
            r++;
        }
        StringBuilder s1 = new StringBuilder();
        if(l>=0){
            s1.append(s.substring(0,l+1));
        }
        if(r<s.length()){
            s1.append(s.substring(r,s.length()));
        }
        return isValid(s1.toString());
    }
    private char getCh(char x){
        switch (x) {
            case '(':
                return ')';
            case '[':
                return ']';
            case '{':
                return '}';
            default:
                return ' ';
        }
    }
}