20. 有效的括号

发表评论
376 views

 ›
20. 有效的括号

官方链接

https://leetcode-cn.com/problems/valid-parentheses/

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

解法一

暴力求解

class Solution {
    public boolean isValid(String s) {

        int len = s.length();
        do {
            len = s.length();
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        } while (len > s.length());
        return s.length() == 0;
    }
}

解法二

使用 stack 数据结构

class Solution:
    def isValid(self, s: str) -> bool:
        m = {
            '(': ')', 
            '{': '}', 
            '[': ']'
        }
        stack = []
        for c in s:
            if c in m:
                stack.append(m[c])
            else:
                if not stack:
                    return False
                if stack.pop() != c:
                    return False
        return not stack

class Solution {
    public boolean isValid(String s) {

        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        Deque<Character> stack = new ArrayDeque<>(); // Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) stack.push(map.get(c));
            else {
                if (stack.isEmpty()) return false;
                Character ch = stack.pop();
                if (c != ch) return false;
            }
        }

        return stack.isEmpty();
    }
}

或者：

class Solution:
    def isValid(self, s: str) -> bool:
      stack = []
      paren_map = {
        ')': '(',
        '}': '{',
        ']': '['
      }
      for c in s:
        if c not in paren_map:
          stack.append(c)
        elif not stack or stack.pop() != paren_map[c]:
            return False
      return not stack

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (!map.containsKey(c)) stack.push(c);
            else {
                if (stack.isEmpty() || stack.pop() != map.get(c)) return false;
            }
        }
        return stack.isEmpty();
    }
}