使用hash表存储括号对应关系
使用栈结构判断括号是否对应

  1. package com.example.suanfa.alg1;
  3. import java.util.Deque;
  4. import java.util.HashMap;
  5. import java.util.LinkedList;
  6. import java.util.Map;
  8. /**
  9.  * @author lfy
  10.  * @date 2022-05-22
  11.  */
  12. public class InvalidParentheses {
  14.     /**
  15.      * 有效的括号
  16.      * @param s
  17.      * @return
  18.      */
  19.     public boolean isValid(String s) {
  21.         int n = s.length();
  22.         if (n%2 != 0){
  23.             return false;
  24.         }
  25.         Map<Character,Character> pair = new HashMap<Character,Character>(){
  26.             {
  27.                 put(')','(');
  28.                 put(']','[');
  29.                 put('}','{');
  30.             }
  33.         };
  34.         Deque<Character> con = new LinkedList<>();
  35.         for (int i = 0; i < n; i++) {
  36.             char c = s.charAt(i);
  37.             if (pair.containsKey(c)){
  38.                 if (con.isEmpty() || con.peek() != pair.get(c)){
  39.                     return false;
  40.                 }
  41.                 con.pop();
  42.             }else {
  43.                 con.push(c);
  44.             }
  45.         }
  46.         return con.isEmpty();
  48.     }
  51.     public static void main(String[] args) {
  52.         String s = "(){}{[]";
  53.         InvalidParentheses test = new InvalidParentheses();
  54.         System.out.println(test.isValid(s));
  55.     }
  56. }

复习

package com.alg.Three;

import java.util.*;

/**
 * 有效的括号
 *
 * @author fuyao
 * @date 2022年06月20日 4:43 下午
 */
public class ValidParentheses {

    public boolean isValid(String s) {
        int length = s.length();
        if (length % 2 != 0) {
            return false;
        }
        Map<Character, Character> contain = new HashMap<Character, Character>() {
            {
                put(')','(');
                put(']','[');
                put('}','{');
            }
        };
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            if (contain.containsKey(s.charAt(i))){
                if (deque.isEmpty() || deque.peek().equals(contain.get(s.charAt(i))) ){
                    return false;
                }
                deque.pop();
            }else {
                deque.push(s.charAt(i));
            }
        }
        return deque.isEmpty();
    }
}