20. 有效的括号

╰+攻爆jí腚メ 2021-11-02 11:58 339阅读 0赞

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

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

1     //方法一：使用栈，成对出现则弹栈，单个出现则入栈，如果是有效的对于括号，则栈最后为空
     2     public static boolean isValid10(String s) {
     3         if(s.isEmpty()) {
     4             return true;
     5         }
     6         //此判断可省略
     7         if(s.length() == 1) {
     8             return false;
     9         }
    10         Map<Character, Integer> dict = new HashMap<>();
    11         dict.put('(', 1);
    12         dict.put(')', 2);
    13         dict.put('[', 4);
    14         dict.put(']', 5);
    15         dict.put('{', 7);
    16         dict.put('}', 8);
    17         Stack<Character> stack = new Stack<>();
    18         for(int i=0; i<s.length(); i++) {
    19             if(stack.isEmpty()) {
    20                 stack.push(s.charAt(i));
    21                 continue;
    22             }
    23             if(dict.get(stack.peek()) == (dict.get(s.charAt(i))-1)) {
    24                 stack.pop();
    25             }else {
    26                 stack.push(s.charAt(i));                
    27             }
    28         }
    29         return stack.isEmpty();
    30     }
    31     
    32     //方法一稍作改进版：将存储的括号字典改进，若遇到闭括号，但此时栈顶不为开括号，则直接返回false
    33     public static boolean isValid11(String s) {
    34         if(s.isEmpty()) {
    35             return true;
    36         }
    37         if(s.length() == 1) {
    38             return false;
    39         }
    40         Map<Character, Character> dict = new HashMap<>();
    41         dict.put(')','(');
    42         dict.put(']','[');
    43         dict.put('}','{');
    44         Stack<Character> stack = new Stack<>();
    45         for(int i=0; i<s.length(); i++) {
    46             if(dict.containsKey(s.charAt(i))) {
    47                 char topChar = stack.isEmpty() ? '*' : stack.pop();
    48                 if(dict.get(s.charAt(i)) != topChar) {
    49                     return false;
    50                 }
    51             }else {
    52                 stack.push(s.charAt(i));
    53             }
    54         }
    55         return stack.isEmpty();
    56     }
    57     
    58     //方法二：使用数组保存开括号，记录当前未匹配开括号的位置，若当前字符为闭括号，则与开括号比对
    59     public boolean isValid2(String s) {
    60         if(s == null || s.length() == 1) {
    61             return false;
    62         }
    63         if(s.isEmpty()) {
    64             return true;
    65         }
    66         Map<Character, Character> dict = new HashMap<>();
    67         dict.put(')','(');
    68         dict.put(']','[');
    69         dict.put('}','{');
    70         int len = s.length();
    71         char[]    arr = new char[len];
    72         int point = 0;
    73         for(int i=0; i<len; i++) {
    74             char c = s.charAt(i);
    75             //若为开括号，直接保存入数组中
    76             if(c == '(' || c == '[' || c == '{') {
    77                 arr[point++] = c;
    78             }
    79             //若为闭括号，则与未匹配的开括号比对，若成功，则将未匹配开括号位置左移一位
    80             else if(point > 0 && (arr[point-1] == dict.get(c))) {
    81                 point--;
    82             }else {
    83                 return false;
    84             }
    85         }
    86         return point == 0;
    87     }

转载于:https://www.cnblogs.com/xiyangchen/p/10850362.html