LeetCode记录之20——Valid Parentheses

09.18更新算法采用栈的思想解决，方法①所示。

本题主要是找是否有匹配的字符串，因为还没有复习到栈之类的知识点，只能还是采用暴力方法了，后期会补上更加优化的算法。我的思路就是先遍历一遍找是否有匹配的符号，有的话就删除，然后继续遍历，直至结束。

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

给定一个字符串，只包含字符“（”、“””、“{”、“}”、“[”和“”），确定输入字符串是否有效。
括号必须以正确的顺序关闭，“（）”和“（）”{“}”都是有效的，但“（）和[（[ ] ] ] ]不是。

①利用栈的思想进行解决。

 1 /*
 2      * 利用栈来进行平衡符号的匹配。
 3      * {[(三种符号是开放字符，)]}是封闭符号。
 4      * 当前字符为开放符号时，入栈。当为封闭符号时，出栈，并与出栈元素进行匹配。
 5      * 当循环结束时，栈为空即所有符号都进行匹配，配对成功。
 6      * */
 7     public boolean isValid(String s){
 8         Stack<Character> chars=new Stack<>();
 9         for(int i=0;i<s.length();i++){
10             char ch=s.charAt(i);
11             switch (ch) {
12             case '(':
13                 chars.push(ch);
14                 break;
15             case ')':
16                 if(chars.empty())
17                     return false;
18                 else {
19                     char getCh=chars.pop();
20                     if(!(getCh=='('))
21                         return false;
22                 }
23                 break;
24             case '[':
25                 chars.push(ch);
26                 break;
27             case ']':
28                 if(chars.empty())
29                     return false;
30                 else {
31                     char getCh=chars.pop();
32                     if(!(getCh=='['))
33                         return false;
34                 }
35                 break;
36             case '{':
37                 chars.push(ch);
38                 break;
39             case '}':
40                 if(chars.empty())
41                     return false;
42                 else {
43                     char getCh=chars.pop();
44                     if(!(getCh=='{'))
45                         return false;
46                 }
47                 break;
48             default:
49                 break;
50             }
51         }
52         if(chars.isEmpty())
53             return true;
54         else
55             return false;
56     }

②利用暴力方式进行解决（不推荐）

 1 public boolean isValid(String s){
 2         int length=s.length();
 3         boolean isDelete=false;
 4         if(length==0||length%2!=0)//判断字符串是否为空或者无法匹配
 5             return false;
 6         while (length >0) {
 7             for (int i = 0; i < length - 1; i++) {
 8                 if ((s.charAt(i) == '(' && s.charAt(i + 1) == ')') || (s.charAt(i) == '{' && s.charAt(i + 1) == '}')
 9                         || (s.charAt(i) == '[' && s.charAt(i + 1) == ']')) {
10                     if(i+2!=length)
11                         s = s.substring(0, i) + s.substring(i + 2, length);//非最后两位字符串截取
12                     else
13                         s = s.substring(0, i);//最后两位字符串截取
14                     length -= 2;//字符串长度减2
15                     isDelete=true;
16                     i=0;//每次将基数归零重新循环
17                 }
18                 else
19                     isDelete=false;//如果循环一次没有任何匹配直接返回false
20             }
21             if (!isDelete)
22                 return false;
23         }
24         return true;
25     }