Leetcode-20 —— Valid Parentheses

Posted on Edited on In ,

Description

Given a string 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.

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 

1
2
3
4
5
6
7
8
9
10
11
// 空字符串 和 null
""
null
// 右括号开头 
")()("
// 字符串长度为奇数
"()()("
// 正常测试用例
"(({}[])())"
// 只有右括号
"(((("

分析

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

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

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

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

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

使用 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() 实现的接口不同，所以方法差异

程序设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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，具体参考如下：

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

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

其他解法