Leetcode-20 —— Valid Parentheses

Description

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1 2	Input: "()" Output: true

Example 2:

1 2	Input: "()[]{}" Output: true

Example 3:

1 2	Input: "(]" Output: false

Example 4:

1 2	Input: "([)]" Output: false

Example 5:

1 2	Input: "{[]}" Output: true

测试用例

根据题意，每个输入都有解，因此数组元素个数一定是大于 2

// 空字符串 和 null
""
null
// 右括号开头 
")()("
// 字符串长度为奇数
"()()("
// 正常测试用例
"(({}[])())"
// 只有右括号
"(((("

分析

如果一个有括号组成的字符串是“有效的”，那么这个字符串应该具有以下特点：

字符串的长度应该是偶数
字符串中的括号有顺序的成对出现

基于以上两个特点，我们只需要遍历字符串，然后检查每个左括号是否有合法的右括号，具体操作时，可以采用消去法，如下图示意，

在没有遇到左括号时，我们不知道它是否能成功配对，因此我们需要先将其存储，直到遇到与之配对的右括号时再消去。从左往右遍历，观察不难发现，多个相连的左括号中，越靠左的越先访问到，却越往后被消去（先进后出），所以我们可以毫不犹豫的选择使用 Stack 存储优先访问到左括号，当遍历完成后，如果 Stack 中的所有左括号都被消去(Stack 为空)，则说明是“有效”字符串。综上所述，得出以下特性，

右括号开头一定不满足
基于 1 的推广，栈空条件下遇到右括号也一定不满足
null 一定不满足，但是题目交代了空字符认为满足
字符串长度为奇数的一定也不满足

使用 Stack 解题

预备知识

位运算判断整数的奇偶性

一个整数在表示为二进制时，某位非 0 即 1，因此该整数和 1 按位与，如果是奇数（末位是1）则结果为 1，否则结果为 0
运算符的优先级

运算符的优先级中， == 优先于 & 优先于 ||

建议：如果记不住优先级顺序可以使用 ()
Java 中的 foreach 循环

遍历数组时，如果我们并不关心每个元素的索引，那么可以使用 foreach，语法如下：
1
2
3
4
5
int[] examples = {100, 101, 102};
for (int x: examples) {
// do something
// x on behalf of each item
}
Java 中的 Stack

想要的操作	提供的方法	备注
查看栈顶元素	peek()
弹出栈顶元素	pop()
压栈	push()
判断栈是否为空	empty() 或者 isEmpty()	实现的接口不同，所以方法差异

程序设计

class Solution {
    public boolean isValid(String s) {
    	if (null == s || (s.length() & 1) == 1 ) {
            return false;
        }
        
        Stack<Character> parentheses = new Stack<>();
        for (char x: s.toCharArray()) {
            if (isLeftBracket(x)) {
                parentheses.push(x);
            } else {
                if (parentheses.empty()) {
                    return false;
                }
                char leftBracket = parentheses.pop();
                if (!isMatch(leftBracket, x)) {
                    return false;
                }
            }
        }
        return parentheses.empty();
    }
}

其中 isLeftBracket() 方法用于判断字符是否是左括号，实现可以参考如下：

1
2
3

private boolean isLeftBracket(char x) {
    return x == '(' || x == '[' || x == '{';
}

isMatch() 用于判断左右两个括号是否匹配，查看了 ASCII 后发现左右括号的 ASCII 相差 1 或 2，具体参考如下：

private boolean isMatch(char left, char right) {
    if (left == '(') {
        return right - left == 1;
    }
    return right - left == 2;
}

提交后，运行时 1ms，打败 98.31%

其他解法

大神们的骚操作