LeetCode----Valid Parentheses
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的时间复杂度和空间复杂度分析:
小结:
1、一开始我在想能不能不用栈来做,可能可以快一点,就想到了想到了下面这种方法
然后写完才发现这个不能满足所有情况,如果是“{[()]}”这种互相包裹的情况没问题,但如果是()[]{}就有问题了,想法不够全面。。。。。。
2、LeetCode要求输入的s为""应该返回true,但我觉得要返回false,因为这个输入不符合要求;
上一篇: Python下连接数据库(mysql)的操作及应用
下一篇: leetcode 1368. Minimum Cost to Make at Least One Valid Path in a Grid
推荐阅读
-
【关于栈】Valid Parentheses详解
-
【关于栈】Valid Parentheses详解
-
LeetCode - 20. Valid Parentheses(0ms)
-
Generate Parentheses(C++)
-
LeetCode-32.Longest Valid Parentheses最长有效括号子串
-
Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)-动态规划
-
算法分析与设计丨第一周丨LeetCode(2)——Different Ways to Add Parentheses(Medium)
-
SyntaxError: Missing parentheses in call to 'print
-
⭐⭐⭐⭐⭐【BFS求最小次数】LeetCode 301. Remove Invalid Parentheses
-
LeetCode1021.Remove Outermost Parentheses(删除最外层的括号)