力扣 有效的括号

括号匹配题目，找到符合的举行抵消。
题目

从题可以看出是嵌套的括号先匹配先做抵消，类似就近原则，这也是栈的典型例题。可以通过摆列多种差别的情况渐渐用if与else做返回。
时间复杂度：O(n)，其中 n 是字符串的长度。空间复杂度：O(n)，重要来自栈的空间。

1. class Solution {
2.    public boolean isValid(String s) {
3.         Stack<Character> stack = new Stack<>();
4.         char[] charArray = s.toCharArray();
6.         for (char ch : charArray) {
7.             //如果是左括号则直接入栈
8.             if (ch == '(' || ch == '{' || ch == '[') {
9.                 stack.push(ch);
10.             } else {
11.                //如果是右括号，并且此时栈不为空
12.                 if (!stack.isEmpty()) {
13.                     if (ch == ')') {
14.                         if (stack.pop() != '(')
15.                             return false;
16.                     } else if (ch == '}') {
17.                         if (stack.pop() != '{')
18.                             return false;
19.                     } else {
20.                         if (stack.pop() != '[')
21.                             return false;
22.                     }
23.                 }
24.                 else{
25.                     return false;
26.                 }
27.             }
28.         }
29.         return stack.isEmpty();
30.     }
31. }

复制代码

通过遍历字符串的字符，把左括号入栈，反面加进的在栈顶，再对右括号出栈看是否可以或许匹配，不匹配就阐明无效，最后还要对栈判空，有可能最后栈还有括号阐明有多的没有匹配到也是不符合的。固然，也可以写简洁一些。

1. class Solution {
2.     public boolean isValid(String s) {
3.         if(s.isEmpty())
4.             return true;
5.         Stack<Character> stack=new Stack<Character>();
6.         for(char c:s.toCharArray()){
7.             if(c=='(')
8.                 stack.push(')');
9.             else if(c=='{')
10.                 stack.push('}');
11.             else if(c=='[')
12.                 stack.push(']');
13.             else if(stack.isEmpty()||c!=stack.pop())
14.                 return false;
15.         }
16.         return stack.isEmpty();
17.     }
18. }

复制代码

 


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。