20-valid-parentheses.md

20. Valid Parentheses - 有效的括号

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

---

题目标签：Stack / String

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
java	37 ms	35 MB

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stk = new Stack<>();
        Map<Character, Character> map = Arrays.stream(new char[][] {{'(', ')'}, {'[', ']'}, {'{', '}'}})
            .collect(Collectors.toMap(kv -> kv[0], kv -> kv[1]));
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                stk.push(c);
            } else {
                if (stk.isEmpty() || c != (map.get(stk.peek()))) return false;
                else stk.pop();
            }
        }
        return stk.isEmpty();
    }
}

Language	Runtime	Memory
python3	44 ms	N/A

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        pair = {'(': ')', '[': ']', '{': '}'}
        for c in s:
            if c in pair:
                stack.append(c)
            else:
                if stack and c == pair[stack[-1]]:
                    stack.pop()
                else:
                    return False
        return not(stack)