20. Valid Parentheses

三刷 07/2022

Version #1 Stack

还是写了两个bug都是在检查stack是否为空的时候出错的

Time O(N)

Space O(N)

Runtime: 2 ms, faster than 90.26% of Java online submissions for Valid Parentheses.

Memory Usage: 41.9 MB, less than 59.00% of Java online submissions for Valid Parentheses.

class Solution {

    public boolean isValid(String s) {

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

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            switch (c) {

                case '(':

                    stack.push(')');

                    break;

                case '[':

                    stack.push(']');

                    break;

                case '{':

                    stack.push('}');

                    break;

                default:

                    if (stack.isEmpty() || stack.pop() != c) {

                        return false;

                    }

            }

        }

        return stack.isEmpty();

    }

}

二刷
Version #2

比Version #1更直观的方法
关键是两个地方check stack是否为空
54.04 %
class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        char[] chars = s.trim().toCharArray();
        Stack<Character> stack = new Stack<>();
     
        for (char c : chars) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                switch (c) {
                    case ')':
                        if (stack.pop() != '(') return false;
                        break;
                    case '}':
                        if (stack.pop() != '{') return false;
                        break;
                    case ']':
                        if (stack.pop() != '[') return false;
                        break;
                    default:
                        return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

一刷
Version #1 如果遇到左括号就push相应的右括号，遇到右括号就看pop()出来的是不是相等
两个有趣的地方

1.Character是char的wrapper

2.switch如果不加break的话就会一直向下执行

public class Solution {

    public boolean isValid(String s) {

        if (s == null || s.length() == 0) return false;

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

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            switch(c) {

                case '(': 

                    stack.push(')');

                    break;

                case '[':

                    stack.push(']');

                    break;

                case '{':

                    stack.push('}');

                    break;

                case ')': 

                case ']': 

                case '}':

                    if (stack.isEmpty() || stack.pop() != c) return false;

            }

        }

        return stack.isEmpty();

        

    }

}

二刷
80.79 %
特别要注意的是如果最后stack不是空的话也是Invalid的
public class Solution {
    public boolean isValid(String s) {
        if (s == null) throw new IllegalArgumentException();
        Stack<Character> stack = new Stack<>();
        char curr;
        for (int i = 0; i < s.length(); i++) {
            curr = s.charAt(i);
            if (curr == '(') stack.push(')');
            else if (curr == '[') stack.push(']');
            else if (curr == '{') stack.push('}');
            else {
                if (stack.isEmpty() || curr != stack.pop()) return false;
            }
        }
        return stack.isEmpty();
    }
}