import java.util.*;

/**

• 給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。

• 有效字符串需滿足：

• 左括號(hào)必須用相同類型的右括號(hào)閉合。

• 左括號(hào)必須以正確的順序閉合。

• 注意空字符串可被認(rèn)為是有效字符串。

• 來(lái)源：力扣（LeetCode）

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

  • 利用棧來(lái)實(shí)現(xiàn)，如果遇見(jiàn)右括號(hào)，判斷棧頂元素是不是對(duì)應(yīng)的左括號(hào)，是則繼續(xù)匹配，不是則返回false

  • 時(shí)間復(fù)雜度：O(n)O(n)，因?yàn)槲覀円淮沃槐闅v給定的字符串中的一個(gè)字符并在棧上進(jìn)行 O(1)O(1) 的推入和彈出操作。

  • 空間復(fù)雜度：O(n)O(n)，當(dāng)我們將所有的開括號(hào)都推到棧上時(shí)以及在最糟糕的情況下，我們最終要把所有括號(hào)推到棧上。例如 ((((((((((

  • @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("()[]{}"));
    }
    }