【嘎】字符串-有效的括号

题目： 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

　　输入: "()"
　　输出: true
示例 2:

　　输入: "()[]{}"
　　输出: true
示例 3:

　　输入: "(]"
　　输出: false
示例 4:

　　输入: "([)]"
　　输出: false
示例 5:

　　输入: "{[]}"
　　输出: true

一开始没有注意到示例5，想的太简单了

 1     public static boolean isValid(String s) {
 2         for (int i = 0; i < s.length(); i+=2) {
 3             System.out.println(s.charAt(i) + "");
 4             System.out.println(s.charAt(i + 1) + "");
 5             if ("(".equals(s.charAt(i) + "")) {
 6                 if (!")".equals(s.charAt(i + 1) + "")) {
 7                     return false;
 8                 }
 9             } else if ("[".equals(s.charAt(i) + "")) {
10                 if (!"]".equals(s.charAt(i + 1) + "")) {
11                     return false;
12                 }
13             } else if ("{".equals(s.charAt(i) + "")) {
14                 if (!"}".equals(s.charAt(i + 1) + "")) {
15                     return false;
16                 }
17             }
18         }
19         return true;
20     }
21     

然后重新写了下面的方法：

 1 class Solution {
 2     public boolean isValid(String s) {
 3         String[] left = new String[s.length()];
 4         String[] right = new String[s.length()];
 5         String a = "({[";
 6         String b = ")}]";
 7         int idx = -1;
 8         for (int i = 0; i < s.length(); i++) {
 9             if (a.indexOf(s.charAt(i) + "") > -1) {
10                 idx++;
11                 left[idx] = s.charAt(i) + "";
12                 right[idx] = b.charAt(a.indexOf(s.charAt(i) + "")) + "";
13             } else if (b.indexOf(s.charAt(i) + "") > -1) {
14                 // 第一个
15                 if (idx == -1) {
16                     return false;
17                 }
18                 if (right[idx].equals(s.charAt(i) + "")) {
19                     idx--; // 比对的时候是镜像的
20                 } else {
21                     return false;
22                 }
23             }
24         }
25         // 一开始没注意还有不闭合的情况
26         if (idx > -1) {
27             return false;
28         }
29         return true;
30     }
31 }

下面是大佬的回答：

1. 数组模拟栈：

 1 public boolean isValid(String s) {
 2
 3         // 空字符串
 4         if (s.length() == 0)
 5             return true;
 6         // 排除奇数长度(位运算)
 7         if ((s.length() & 1) == 1)
 8             return false;
 9
10         // 栈元素个数
11         int index = 0;
12         // 栈
13         char[] stack = new char[s.length()];
14
15         for (int i = 0; i < s.length(); i++) {
16             switch (s.charAt(i)) {
17                 case '(':
18                 case '[':
19                 case '{':
20                     // 进栈
21                     stack[index++] = s.charAt(i);
22                     continue;
23                 case ')':
24                     if (index == 0 || stack[--index] != '(')
25                         return false;
26                     // stack[--index] == '(' ，才会contniue
27                     // --index：相当于满足的元素出栈
28                     continue;
29                 case ']':
30                     if (index == 0 || stack[--index] != '[')
31                         return false;
32                     continue;
33                 case '}':
34                     if (index == 0 || stack[--index] != '{')
35                         return false;
36                     continue;
37             }
38         }
39
40         return index == 0; // 判断栈是否为空
41     }

2. 栈的写法：

 1 class Solution {
 2     public boolean isValid(String s) {
 3         if (s.length() == 0)
 4             return true;
 5         if ((s.length() & 1) == 1)
 6             return false;
 7         Stack<Character> stack = new Stack<>();
 8         for (int i = 0; i < s.length(); i++) {
 9             switch (s.charAt(i)) {
10                 case '(':
11                 case '[':
12                 case '{':
13                     stack.push(s.charAt(i));
14                     continue;
15                 case ')':
16                     if (stack.isEmpty() || stack.pop() != '(')
17                         return false;
18                     continue;
19                 case ']':
20                     if (stack.isEmpty() || stack.pop() != '[')
21                         return false;
22                     continue;
23                 case '}':
24                     if (stack.isEmpty() || stack.pop() != '{')
25                         return false;
26                     continue;
27             }
28         }
29         return stack.isEmpty();
30     }
31 }

// 在switch case 语句中不能使用continue 关键字。continue语句的作用是跳出本次循环，转入执行下一次循环。除非是在for循环下。

每个case都要记得加break~