Skip to content

Latest commit

 

History

History
142 lines (103 loc) · 3.22 KB

File metadata and controls

142 lines (103 loc) · 3.22 KB

English Version

题目描述

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

有效字符串需满足:

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

 

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

 

提示:

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

解法

栈实现。

遍历括号字符串,遇到左括号时,将左括号压入栈中;遇到右括号时,弹出栈顶元素(栈若为空,直接返回 false),判断是否是相同类型的括号。若不匹配,直接返回 false。

遍历结束,栈若为空,说明括号字符串有效。

Python3

class Solution:
    def isValid(self, s: str) -> bool:
        q = []
        parentheses = {'()', '[]', '{}'}
        for ch in s:
            if ch in '([{':
                q.append(ch)
            elif not q or q.pop() + ch not in parentheses:
                return False
        return not q

Java

class Solution {
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        Deque<Character> q = new ArrayDeque<>();
        for (char ch : chars) {
            boolean left = ch == '(' || ch == '[' || ch == '{';
            if (left) q.push(ch);
            else if (q.isEmpty() || !match(q.pop(), ch)) return false;
        }
        return q.isEmpty();
    }

    private boolean match(char l, char r) {
        return (l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']');
    }
}

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> q;
        for (int i = 0, n = s.length(); i < n; ++i) {
            if (s[i] == '{' || s[i] == '[' || s[i] == '(') q.push(s[i]);
            else if (q.empty() || !match(q.top(), s[i])) return false;
            else q.pop();
        }
        return q.empty();
    }
private:
    bool match(char l, char r) {
        return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}');
    }
};

...