有效括号

import java.util.*;

/**

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

• 有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。

• 左括号必须以正确的顺序闭合。

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

• 来源：力扣（LeetCode）

• 链接：https://leetcode-cn.com/problems/valid-parentheses
  /
  public class EffectiveBrackets {
  /*

  • 利用栈来实现，如果遇见右括号，判断栈顶元素是不是对应的左括号，是则继续匹配，不是则返回false

  • 时间复杂度：O(n)O(n)，因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1)O(1) 的推入和弹出操作。

  • 空间复杂度：O(n)O(n)，当我们将所有的开括号都推到栈上时以及在最糟糕的情况下，我们最终要把所有括号推到栈上。例如 ((((((((((

  • @param s

  • @return
    */
    public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    Map<Character,Character> correctBrackets = new HashMap<>();
    correctBrackets.put(')','(');
    correctBrackets.put(']','[');
    correctBrackets.put('}','{');
    for(int i=0;i<s.length();i++) {
    char c = s.charAt(i);
    if(correctBrackets.containsKey(c)){
    if(stack.isEmpty()||stack.pop()!=correctBrackets.get(c)) return false;
    }else stack.push(c);

    }
    return stack.isEmpty();
    }
    public static void main(String[] args){
    EffectiveBrackets effectiveBrackets = new EffectiveBrackets();
    System.out.println(effectiveBrackets.isValid("()[]{}"));
    }
    }