20. 有效的括号

image.png
image.png

替换字符串法

  1. class Solution {
  2.     // 将成对的括号替换成空
  3.     // 如果整个字符串都能被替换成空说明给定的字符串有效
  4.     // 如果出现无法替换的情况说明字符串无效
  5.     public boolean isValid(String s) {
  6.         while (s.length() > 0) {
  7.             if (s.contains("()")) {
  8.                 s = s.replace("()", "");
  9.             } else if (s.contains("[]")) {
  10.                 s = s.replace("[]", "");
  11.             } else if (s.contains("{}")) {
  12.                 s = s.replace("{}", "");
  13.             } else {
  14.                 return false;
  15.             }
  16.         }
  17.         return true;
  18.     }
  19. }

使用辅助栈

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty()) {
                if (c == ')' && stack.peek() == '(') {
                    stack.pop();
                    continue;
                } else if (c == ']' && stack.peek() == '[') {
                    stack.pop();
                    continue;
                } else if (c == '}' && stack.peek() == '{') {
                    stack.pop();
                    continue;
                }
            } 
            stack.push(c);
        }
        return stack.isEmpty();
    }
}

使用辅助栈，if 块的另一种写法

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()) {
            if (!stack.isEmpty()) {
                if ((c == ')' && stack.peek() == '(') 
                    || (c == ']' && stack.peek() == '[')
                    || (c == '}' && stack.peek() == '{')) {
                    stack.pop();
                    continue;
                }
            }
            stack.push(c);    
        }
        return stack.isEmpty();
    }
}