括号相关的算法题

1. 判断合法括号串 letcode 20

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

   有效字符串需满足：

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

   示例

   1. 输入：s = "()"
      输出：true
   2. 输入：s = "()[]{}"
      输出：true
   3. 输入：s = "(]"
      输出：false
   

   思路：采用栈先入后出，如果遇到左括号入栈，遇到右括号时对应栈顶的左括号需要出栈，需要遍历完所有，stack同样为空。

   算法：

private final static Map<Character, Character> map = new HashMap<Character, Character>() {
        {
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }
    };
    public static boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) { // 奇数不是有效
            return false;
        }
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
              // 有效的字符必定栈顶当前循环的字符成对。
                if (stack.isEmpty() || !stack.peek().equals(map.get(c))) {  
                    return false;
                }
                stack.pop(); // 出栈
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

2. 使括号有效的最小填充 letcode 921

   描述：给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

   从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

   • 它是一个空字符串
   • 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，
   • 它可以被写作 (A)，其中 A 是有效字符串。 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

   示例：

   1. 输入："())"
      输出：1
   2. 输入："((("
      输出：3
   3. 输入："()))(("
      输出：4
   

   思路：定义一个栈，用来存储"(" , 遍历字符串s，当遇到"(" 则进栈，如果是")"则判断当前栈是否为空，不为空，则表示存在与当前右括号匹配的左括号，匹配后栈顶出栈。若为空，则表示没有能与"("匹配的，此时需要进行记录count。
   遍历完字符串s，找到未匹配到")"的数量；如果栈不为空，说明有未匹配到"(",需要返回栈大小,最后两数相加就是结果。

public static int minAddToMakeValid(String s) {
    int n = s.length();
    int count = 0;
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '(') {
            stack.push(s.charAt(i));
        }
        if (s.charAt(i) == ')') {
            if (!stack.isEmpty()) {
                stack.pop();
            } else {
                count++;
            }

        }
    }
    return stack.isEmpty() ? count : stack.size() + count;
}