欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode----Valid Parentheses

程序员文章站 2022-05-18 09:28:08
...

Valid Parentheses

今天做了一道LeetCode上easy题,要求是判断括号是否匹配
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

思路:

第一步:判断if(s==null)是则返回false;
第二步:定义一个Stack braces=new Stack<>()栈,遍历s,如果遇到左边的括号则入栈,遇到右边的括号则判断栈顶元素是不是匹配的左括号if(braces.peek()!=(s.charAt(i)-1)&&braces.peek()!=(s.charAt(i)-2)),如果是则出栈,如果不是则ruturn false;如果期间栈空但s还没有遍历完则return false;
第三步:如果遍历完s之后栈还没空,说明左括号多于右括号,return false;
第四步:能走到这里说明没有问题,return true;

代码:

import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
        if(s==null)
            return false;
        int i=0;
        Stack<Character> braces=new Stack<>();
        while(i<s.length()){
            if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{')
                braces.push(s.charAt(i));
            else if(s.charAt(i)==')'||s.charAt(i)==']'||s.charAt(i)=='}'){
                if(braces.empty())
                    return false;
               	//使用了ASCII码的关系来判断是否是对应的左右括号
                else if(braces.peek()!=(s.charAt(i)-1)&&braces.peek()!=(s.charAt(i)-2))
                     return false;   
                else
                    braces.pop();
            }  
            i++;
        }
       if(!braces.empty())
            return false; 
       return true;
    }
}

LeetCode的时间复杂度和空间复杂度分析:
LeetCode----Valid Parentheses

小结:
1、一开始我在想能不能不用栈来做,可能可以快一点,就想到了想到了下面这种方法
LeetCode----Valid Parentheses
然后写完才发现这个不能满足所有情况,如果是“{[()]}”这种互相包裹的情况没问题,但如果是()[]{}就有问题了,想法不够全面。。。。。。

2、LeetCode要求输入的s为""应该返回true,但我觉得要返回false,因为这个输入不符合要求;