leetcode每日一题-20:有效的括号

leetcode每日一题-20:有效的括号 leetcode每日一题-20:有效的括号 链接 有效的括号

题目

分析

这个题目是栈的经典应用。我们每次遇到右括号的时候将他加到栈中，每日遇到左括号的时候，取出栈顶（也就是和当前右括号距离最近的左括号），看看是否对应，如果此时栈顶不存在，也就说明右括号少于左括号，一定不合法，如果不匹配，那么也一定不合法。等遍历结束的时候，如果栈中还有元素剩余，那么说明右括号多于左括号，那么这也不合法。综上就可以判断出这个字符串是否合法了。

代码

C++

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        stack stk;

        for(int i=0 ; i 

 
 
 
Java
 
 
class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map pairs = new HashMap() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque stack = new linkedList();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

作者：LeetCode-Solution
 

 
 
 
Golang
 
 
func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{}
    for i := 0; i < n; i++ {
        if pairs[s[i]] > 0 {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

作者：LeetCode-Solution
 

 
 
 
Python
 
 
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)
        
        return not stack

作者：LeetCode-Solution
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5490921.html