LeetCode 020 Valid Parentheses

Valid Parentheses

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:Input: "()"
Output: true
----------------------------------
Example 2:Input: "()[]{}"
Output: true
----------------------------------
Example 3:Input: "(]"
Output: false
---------------------------------
Example 4:Input: "([)]"
Output: false
---------------------------------
Example 5:Input: "{[]}"
Output: true

题目分析

很简单的题目，使用栈就可以很好地解决，遇见左括号则入栈，遇见右括号则弹栈。

• 弹栈后检测是否匹配，成功则继续检测，失败则返回false。
• 检测完成后看栈是否为空，若不为空则说明左括号富裕，不合格，返回false。
• 全部通过则返回true。

有一个地方，我在做左右匹配的时候，是用ascll表，观察得左右匹配好的括号相差在一和二左右。
所以有了下面的检测方式。

public class leetcode20 {
    public boolean isValid(String s) {
    Stack <Character>stack = new Stack();char temp [] = s.toCharArray();for(int i = 0;i<temp.length;i++){
    if(temp[i]=='('||temp[i]=='['||temp[i]=='{')stack.push(temp[i]);else {
    if(stack.empty())//存在右括号，但是左括号为零，则不匹配return false;char compare = stack.pop();//这里取巧的地方是查ascll表，发现匹配好的左右括号相差一或者二，// 而且输入的字符串中保证只有括号，所以可以进行这样的转换比较if(compare!=temp[i]-1&&compare != temp[i]-2)return false;}}if(!stack.empty())//如果最后发现栈不为空，则左括号还有剩余，不符合return false;return true;//所有的都通过，则匹配成功}}