题目

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

方法一、栈

思路

拿到前半部分就入栈，拿到后半部分就和栈顶的元素对比，如果是一对就出栈，不是一对就继续入栈。
需要注意的是，这个字符串的长度一定会是偶数才有可能返回true，奇数一定是false，这点是我没有想到的，看了一下官方解析恍然大悟。

代码

  1. public boolean isValid(String str) {
  3.     int n = str.length();
  4.     if (n % 2 == 1) {
  5.         return false;
  6.     }
  8.     Map<Character, Character> map = new HashMap<Character, Character>() {{
  9.         put(']', '[');
  10.         put(')', '(');
  11.         put('}', '{');
  12.     }};
  14.     Stack<Character> stack = new Stack<>();
  15.     char[] charArray = str.toCharArray();
  16.     for (char c : charArray) {
  18.         if(stack.isEmpty()){
  19.             stack.push(c);
  20.             continue;
  21.         }
  23.         // 如果是前半部分直接push
  24.         // 后半部分就拿到前半部分再对比,是一对就pop，不是一对就push
  25.         if(map.containsKey(c) && map.get(c).equals(stack.peek())){
  26.             stack.pop();
  27.         }else {
  28.             stack.push(c);
  29.         }
  30.     }
  31.     return stack.empty();
  32. }

复杂度分析

时间复杂度：O(n)，其中 nn 是字符串 ss 的长度。
空间复杂度O(n+∣Σ∣)，其中Σ 表示字符集，本题中字符串只包含 66 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

方法二、字符串替换

可以实现，但没有必要。。。效率有点低。

思路

如果符合条件的话，必然至少有一对符号是连续的，并且符号都是两个成一对，以这一点为突破口，循环去把成对的去掉。

代码

public boolean isValid(String s) {
    if(s.length() < 2 || s.length()%2 != 0){
        if(s.isEmpty()){
            return true;
        }
        return false;
    }
    int count = 0;
    int length = s.length();
    while(count < length/2){
        s = s.replace("{}","").replace("[]","").replace("()","");
        count++;
    }

    if(s.length()>0){
        return false;
    }
    return true;
}