LeetCode 20. 有效的括号

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

解法思路:

1. 暴力：不断 replace 匹配的括号 -> ""   O(n^2)

   a. ()[]{}

   b. ((({[]}))) true

2. Stack. O(n) 

法一:

class Solution {
    public boolean isValid(String s) {
        // Time: O(n^2)
        int len = s.length();
        if (len % 2 != 0) {
            return false;
        }
        int n = len / 2;
        for (int i = 0; i < n; i++) {
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");
        }
        return s.length() == 0;
    }
}

 法二:

class Solution {
    public boolean isValid(String s) {
        // stack
        // O(n)
        int len = s.length();
        if (len % 2 != 0) {
            return false;
        }
        Map<Character, Character> pairs = new HashMap<Character, Character>() {
  {
                put(')', '(');
                put(']', '[');
                put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.addFirst(ch);
            }
        }
        return stack.isEmpty();
    }
}