algorithm-series-bracket

括号相关问题

20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

class Solution {
    public boolean isValid(String s) {  // 栈
        char cs[] = s.toCharArray();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '('); map.put('}', '{'); map.put(']', '[');
        Deque<Character> stack = new LinkedList<>();
        for (char c : cs) {
            Character match = map.get(c);
            if (match == null) {
                stack.push(c);
            }
            else {
                if (!stack.isEmpty() && stack.peek().equals(match)) {
                    stack.pop();
                }
                else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

class Solution {
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {  // dfs
        dfs(n, n, "");
        return res;
    }
    public void dfs(int left, int right, String s) {  // left和right分别表示左右括号剩余数量，s是当前构造的字符串
        if (left == 0 && right == 0) {
            res.add(s);
            return;
        }
        if (left > 0) dfs(left-1, right, s+"(");
        if (right > 0 && right > left) dfs(left, right-1, s+")");
    }
}

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 10^4
• s[i] 为 '(' 或 ')'

class Solution {
    public int longestValidParentheses(String s) {  // 栈
        char[] cs = s.toCharArray();
        int n = cs.length;
        Deque<Integer> stack = new LinkedList<>();  // 存储左括号的位置
        int res = 0, pre = -1;  // pre表示上一次不匹配的位置
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();  // 括号匹配，弹出
                    int left = pre;  // 区间的左边界
                    if (!stack.isEmpty()) left = stack.peek();  // 如果栈还有元素，则更新左边界
                    res = Math.max(res, i - left);  // 用当前区间长度更新结果
                } else {
                    pre = i;  // 更新上一次不匹配的位置
                }
            }
        }
        return res;
    }
}

class Solution {
    public int longestValidParentheses(String s) {  // 动态规划
        char[] cs = s.toCharArray();
        int n = cs.length;
        // f[i]: 以位置i-1的结尾的最长有效子串长度
        int[] f = new int[n+1];
        for (int i = 1; i < n; i++) {
            if (cs[i] == '(') continue;
            if (cs[i-1] == '(') {  // ***()：和前一个字符匹配
                f[i+1] = f[i-1] + 2;
            } else {  // ***))：和前一个字符不匹配
                if (i-f[i]-1 >= 0 && cs[i-f[i]-1] == '(') {  // 查看前一个字符对应的位置的前一个位置是不是'('
                    f[i+1] = f[i] + 2 + f[i-f[i]-1];
                }
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }
}

class Solution {
    public int longestValidParentheses(String s) {  // 计数解法
        char[] cs = s.toCharArray();
        int n = cs.length;
        int res = 0, left = 0, right = 0;
        for (int i = 0; i < n; i++) {  // 从左到右，计算左右括号的数量
            if (cs[i] == '(') left++;
            else right++;
            if (left == right) res = Math.max(res, left + right);  // 如果相等，更新答案
            if (left < right) {  // 如果右括号更多，则无效，都置零
                left = 0; right = 0;
            }
        }
        // 最后可能有剩余的左右括号，没有计算，所以同理反序遍历
        left = 0; right = 0;
        for (int i = n-1; i >= 0; i--) {
            if (cs[i] == '(') left++;
            else right++;
            if (left == right) res = Math.max(res, left + right);
            if (left > right) {  // 条件反过来
                left = 0; right = 0;
            }
        }
        return res;
    }
}

301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

class Solution {
    List<String> res = new ArrayList<>();
    int maxLen = 0;
    public List<String> removeInvalidParentheses(String s) {
        char[] cs = s.toCharArray();
        dfs(cs, 0, 0, "");
        return res;
    }
    public void dfs(char[] cs, int cur, int balance, String s) {
        int n = cs.length;
        if (balance < 0) return;  // 左括号数量小于右括号
        if (cur == n) {
            if (balance == 0) {  // 左右括号匹配
                if (s.length() > maxLen) {  // 当前匹配字符串更长，更新长度和结果
                    maxLen = s.length();
                    res.clear();
                }
                if (s.length() == maxLen && !res.contains(s)) res.add(s);  // 长度满足，添加当前结果（去重）
            }
            return;
        }
        if (cs[cur] == '(' || cs[cur] == ')') dfs(cs, cur+1, balance, s);  // 跳过当前字符
        if (cs[cur] == '(') {
            dfs(cs, cur+1, balance+1, s+"(");
        } else if (cs[cur] == ')') {
            dfs(cs, cur+1, balance-1, s+")");
        } else {
            dfs(cs, cur+1, balance, s+cs[cur]);
        }
    }
}

678. 有效的括号字符串

给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回 true 。

有效 字符串符合如下规则：

• 任何左括号 '(' 必须有相应的右括号 ')'。
• 任何右括号 ')' 必须有相应的左括号 '(' 。
• 左括号 '(' 必须在对应的右括号之前 ')'。
• '*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串 ""。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "(*)"
输出：true

示例 3：

输入：s = "(*))"
输出：true

提示：

• 1 <= s.length <= 100
• s[i] 为 '('、')' 或 '*'

class Solution {
    public boolean checkValidString(String s) {  // 贪心
        char[] cs = s.toCharArray();
        int min = 0, max = 0;  // 左括号个数的上下界
        for (char c : cs) {
            if (c == '(') {
                min++; max++;
            } else if (c == ')') {
                min--; max--;
            } else if (c == '*') {
                min--; max++;
            }
            min = Math.max(min, 0);  // 左括号个数不能小于0
            if (max < 0) return false;  // 右括号过多
        }
        return min == 0;  // 如果左括号个数的下界等于0，则可以匹配
    }
}

class Solution {
    public boolean checkValidString(String s) {  // 记忆化搜索
        char[] cs = s.toCharArray();
        int[][][] memo = new int[101][101][101];
        return dfs(cs, 0, 0, 0, memo);
    }
    public boolean dfs(char[] cs, int cur, int left, int right, int[][][] memo) {
        if (memo[cur][left][right] != 0) return memo[cur][left][right] == 1;
        int n = cs.length;
        if (right > left) return false;
        if (cur == n) return left == right;
        boolean res = false;
        if (cs[cur] == '(') res = dfs(cs, cur+1, left+1, right, memo);
        else if (cs[cur] == ')') res = dfs(cs, cur+1, left, right+1, memo);
        else res = dfs(cs, cur+1, left+1, right, memo) || dfs(cs, cur+1, left, right+1, memo) || dfs(cs, cur+1, left, right, memo);
        memo[cur][left][right] = res ? 1 : 2;
        return res;
    }
}

class Solution {
    public boolean checkValidString(String s) {  // 记忆化搜索对应的动态规划
        char[] cs = s.toCharArray();
        int n = cs.length;
        // f[i][j][k]: 对于s[:i)来说，左右括号数量分别为j和k，是否出现过
        boolean[][][] f = new boolean[n+1][n+1][n+1];
        f[0][0][0] = true;  // 空字符串，左右括号数量分别为0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k <= j; k++) {
                    if (cs[i] == '(') {
                        f[i+1][j+1][k] |= f[i][j][k];
                    } else if (cs[i] == ')') {
                        f[i+1][j][k+1] |= f[i][j][k];
                    } else if (cs[i] == '*') {
                        f[i+1][j+1][k] |= f[i][j][k];
                        f[i+1][j][k+1] |= f[i][j][k];
                        f[i+1][j][k] |= f[i][j][k];
                    }   
                }
            }
        }
        for (int i = 0; i <= n; i++) {  // 只要有左右括号数量相等的情况，返回true
            if (f[n][i][i]) return true;
        }
        return false;
    }
}

class Solution {
    public boolean checkValidString(String s) {  // 另一种的动态规划，只需要括号数量差别作为状态
        char[] cs = s.toCharArray();
        int n = cs.length;
        // f[i][j]: 对于s[:i)来说，左括号数量比右括号多j个的可能性
        boolean[][] f = new boolean[n+1][n+1];
        f[0][0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (cs[i] == '(') {
                    f[i+1][j+1] |= f[i][j];
                } else if (cs[i] == ')') {
                    if (j-1 >= 0) f[i+1][j-1] |= f[i][j];
                } else if (cs[i] == '*') {
                    f[i+1][j+1] |= f[i][j];
                    if (j-1 >= 0) f[i+1][j-1] |= f[i][j];
                    f[i+1][j] |= f[i][j];
                }
            }
        }
        return f[n][0];
    }
}