如何解决括号相关的问题

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode 力扣 难度
1541. Minimum Insertions to Balance a Parentheses String 1541. 平衡括号字符串的最少插入次数 🟠
20. Valid Parentheses 20. 有效的括号 🟢
921. Minimum Add to Make Parentheses Valid 921. 使括号有效的最少添加 🟠

———–

判断有效括号串

对括号的有效性判断多次在笔试中出现,现实中也很常见,比如说我们写的代码,编辑器会检查括号是否正确闭合。而且我们的代码可能会包含三种括号 [](){},判断起来有一点难度。

来看一看力扣第 20 题「 有效的括号」,输入一个字符串,其中包含 [](){} 六种括号,请你判断这个字符串组成的括号是否有效。

举几个例子:

Input: "()[]{}"
Output: true

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

解决这个问题之前,我们先降低难度,思考一下,如果只有一种括号 (),应该如何判断字符串组成的括号是否有效呢?

假设字符串中只有圆括号,如果想让括号字符串有效,那么必须做到:

每个右括号 ) 的左边必须有一个左括号 ( 和它匹配

比如说字符串 ()))(( 中,中间的两个右括号左边就没有左括号匹配,所以这个括号组合是无效的。

那么根据这个思路,我们可以写出算法:

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

/**
* 一个字符串合法括号字符串的条件:
* 1. 左右括号数量相等;
* 2. 任意一个位置左括号的数量都大于等于右括号的数量。
*/

/**
 * 定义一个函数,检验字符串是否为合法括号字符串
 * @param str 待检验的字符串
 * @return boolean 类型,是/否合法括号字符串
 */
boolean isValid(String str) {
    // 待匹配的左括号数量
    int left = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == '(') {
            left++;
        } else {
            // 遇到右括号
            left--;
        }

        // 右括号太多
        if (left == -1)
            return false;
    }
    // 是否所有的左括号都被匹配了
    return left == 0;
}
bool isValid(string str) {
    // 待匹配的左括号数量
    int left = 0;
    for (int i = 0; i < str.size(); i++) {
        if (s[i] == '(') {
            left++;
        } else {
            // 遇到右括号
            left--;
        }

        // 右括号太多
        if (left == -1)
            return false;
    }
    // 是否所有的左括号都被匹配了
    return left == 0;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

def is_valid(str):
    # 待匹配的左括号数量
    left = 0
    for i in range(len(str)):
        if str[i] == '(':
            left += 1
        else:
            # 遇到右括号
            left -= 1
        # 右括号太多
        if left == -1:
            return False
    # 是否所有的左括号都被匹配了
    return left == 0
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

func isValid(str string) bool {
    // 待匹配的左括号数量
    left := 0
    for i := 0; i < len(str); i++ {
        if str[i] == '(' {
            left++
        } else {
            // 遇到右括号
            left--
        }
        // 右括号太多
        if left == -1 {
            return false
        }
    }
    // 是否所有的左括号都被匹配了
    return left == 0
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

/**
 * 待匹配的左括号数量
 * @param {string} str
 * @returns {boolean}
 */
var isValid = function(str) {
    var left = 0;

    for (var i = 0; i < str.length; i++) {
        if (str[i] == '(') {
            left++;
        } else {
            // 遇到右括号
            left--;
        }

        // 右括号太多
        if (left == -1) {
            return false;
        }
    }

    // 是否所有的左括号都被匹配了
    return left == 0;
};

如果只有圆括号,这样就能正确判断有效性。对于三种括号的情况,我一开始想模仿这个思路,定义三个变量 left1left2left3 分别处理每种括号,虽然要多写不少 if else 分支,但是似乎可以解决问题。

但实际上直接照搬这种思路是不行的,比如说只有一个括号的情况下 (()) 是有效的,但是多种括号的情况下, [(]) 显然是无效的。

仅仅记录每种左括号出现的次数已经不能做出正确判断了,我们要加大存储的信息量,可以利用栈来模仿类似的思路。栈是一种先进后出的数据结构,处理括号问题的时候尤其有用。

我们这道题就用一个名为 left 的栈代替之前思路中的 left 变量,遇到左括号就入栈,遇到右括号就去栈中寻找最近的左括号,看是否匹配

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

boolean isValid(String str) {
    Stack<Character> left = new Stack<>();
    for (char c : str.toCharArray()) {
        if (c == '(' || c == '{' || c == '[')
            left.push(c);
        else { // 字符 c 是右括号
            if (!left.empty() && leftOf(c) == left.peek())
                left.pop();
            else
                // 和最近的左括号不匹配
                return false;
        }
    }
    // 是否所有的左括号都被匹配了
    return left.empty();
}

char leftOf(char c) {
    if (c == '}') return '{';
    if (c == ')') return '(';
    return '[';
}
bool isValid(string str) {
    stack<char> left;
    for (char c : str) {
        if (c == '(' || c == '{' || c == '[')
            left.push(c);
        else { // 字符 c 是右括号
            if (!left.empty() && leftOf(c) == left.top())
                left.pop();
            else
                // 和最近的左括号不匹配
                return false;
        }
    }
    // 是否所有的左括号都被匹配了
    return left.empty();
}

char leftOf(char c) {
    if (c == '}') return '{';
    if (c == ')') return '(';
    return '[';
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

def isValid(s: str) -> bool:
    left = [] # 存放左括号
    for c in s:
        if c == '(' or c == '{' or c == '[': # 判断是否为左括号
            left.append(c) # 是左括号则加入列表
        else: # 是右括号
            if left and leftOf(c) == left[-1]: # 判断是否与最近的左括号匹配
                left.pop() # 匹配则将最近的左括号弹出
            else:
                return False # 不匹配则直接返回 false
    return not left # 是否所有的左括号都被匹配了

def leftOf(c: str) -> str:
    if c == '}': 
        return '{'
    elif c == ')':
        return '('
    else:
        return '['
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

func isValid(str string) bool {
    left := make([]byte, 0)
    for i := 0; i < len(str); i++ {
        if str[i] == '(' || str[i] == '{' || str[i] == '[' {
            left = append(left, str[i])
        } else {
            // 字符 c 是右括号
            if len(left) != 0 && leftOf(str[i]) == left[len(left)-1] {
                left = left[:len(left)-1]
            } else {
                // 和最近的左括号不匹配
                return false
            }
        }
    }
    // 是否所有的左括号都被匹配了
    return len(left) == 0
}

func leftOf(c byte) byte {
    if c == '}' {
        return '{'
    }
    if c == ')' {
        return '('
    }
    return '['
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

function isValid(str) {
    var left = [];
    for (var i = 0; i < str.length; i++) {
        var c = str.charAt(i);
        if (c === '(' || c === '{' || c === '[')
            left.push(c);
        else { // 字符 c 是右括号
            if (left.length !== 0 && leftOf(c) === left[left.length - 1])
                left.pop();
            else
                // 和最近的左括号不匹配
                return false;
        }
    }
    // 是否所有的左括号都被匹配了
    return left.length === 0;
}

function leftOf(c) {
    if (c === '}') return '{';
    if (c === ')') return '(';
    return '[';
}

👾 代码可视化动画 👾

接下来讲另外两个常见的问题,如何通过最小的插入次数将括号变成有效的?

平衡括号串(一)

先来个简单的,力扣第 921 题「 使括号有效的最少添加」:

给你输入一个字符串 s,你可以在其中的任意位置插入左括号 ( 或者右括号 ),请问你最少需要几次插入才能使得 s 变成一个有效的括号串?

比如说输入 s = "())(",算法应该返回 2,因为我们至少需要插入两次把 s 变成 "(())()",这样每个左括号都有一个右括号匹配,s 是一个有效的括号串。

这其实和前文的判断括号有效性非常类似,我们直接看代码:

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

/**
 * 给定一个由 '(' 和 ')' 括号组成的字符串 S,我们需要添加最少的括号( '(' 或是 ')',可以在任何位置),以使得到的括号字符串有效。
 * 在完成此题时,保证输入始终是有效的。
 * 
 * 示例:
 * 输入:"())"
 * 输出:1
 */
public int minAddToMakeValid(String S) {
    // 记录插入次数
    int res = 0;
    // 变量记录右括号的需求量
    int need = 0;

    for (int i = 0; i < S.length(); i++) {
        if (S.charAt(i) == '(') {
            // 对右括号的需求 + 1
            need++;
        }

        if (S.charAt(i) == ')') {
            // 对右括号的需求 - 1
            need--;

            if (need == -1) {
                need = 0;
                // 需插入一个左括号
                res++;
            }
        }
    }

    // 插入剩余所需的右括号
    return res + need;
}
int minAddToMakeValid(string s) {
    // res 记录插入次数
    int res = 0;
    // need 变量记录右括号的需求量
    int need = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            // 对右括号的需求 + 1
            need++;
        }
        
        if (s[i] == ')') {
            // 对右括号的需求 - 1
            need--;

            if (need == -1) {
                need = 0;
                // 需插入一个左括号
                res++;
            }
        }
    }
    
    return res + need;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

def minAddToMakeValid(s: str) -> int:
    # res 记录插入次数
    res = 0
    # need 变量记录右括号的需求量
    need = 0

    for i in range(len(s)):
        if s[i] == '(':
            # 对右括号的需求 + 1
            need += 1
        elif s[i] == ')':
            # 对右括号的需求 - 1
            need -= 1
            if need == -1:
                need = 0
                # 需插入一个左括号
                res += 1
    
    return res + need
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

func minAddToMakeValid(s string) int {
    // res 记录插入次数
    res := 0
    // need 变量记录右括号的需求量
    need := 0

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            // 对右括号的需求 + 1
            need++
        }
        
        if s[i] == ')' {
            // 对右括号的需求 - 1
            need--
            if need == -1 {
                need = 0
                // 需插入一个左括号
                res++
            }
        }
    }
    
    return res + need
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

// 使用 var 声明函数
var minAddToMakeValid = function(s) {
    // res 记录插入次数
    let res = 0;
    // need 变量记录右括号的需求量
    let need = 0;

    for (let i = 0; i < s.length; i++) {
        if (s[i] == '(') {
            // 对右括号的需求 + 1
            need++;
        }
        
        if (s[i] == ')') {
            // 对右括号的需求 - 1
            need--;

            if (need == -1) {
                need = 0;
                // 需插入一个左括号
                res++;
            }
        }
    }
    
    return res + need;
};

👾 代码可视化动画 👾

这段代码就是最终解法,核心思路是以左括号为基准,通过维护对右括号的需求数 need,来计算最小的插入次数。需要注意两个地方:

1、当 need == -1 的时候意味着什么

因为只有遇到右括号 ) 的时候才会 need--need == -1 意味着右括号太多了,所以需要插入左括号。

比如说 s = "))" 这种情况,需要插入 2 个左括号,使得 s 变成 "()()",才是一个有效括号串。

2、算法为什么返回 res + need

因为 res 记录的左括号的插入次数,need 记录了右括号的需求,当 for 循环结束后,若 need 不为 0,那么就意味着右括号还不够,需要插入。

比如说 s = "))(" 这种情况,插入 2 个左括号之后,还要再插入 1 个右括号,使得 s 变成 "()()()",才是一个有效括号串。

以上就是这道题的思路,接下来我们看一道进阶题目,如果左右括号不是 1:1 配对,会出现什么问题呢?

平衡括号串(二)

这是力扣第 1541 题「 平衡括号字符串的最少插入次数」:

现在假设 1 个左括号需要匹配 2 个右括号才叫做有效的括号组合,那么给你输入一个括号串 s,请问你如何计算使得 s 有效的最小插入次数呢?

核心思路还是和刚才一样,通过一个 need 变量记录对右括号的需求数,根据 need 的变化来判断是否需要插入

第一步,我们按照刚才的思路正确维护 need 变量:

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

// 字符串s和字符串t
// 返回使得s中出现t的不同子序列个数的最小值
// 用dp_dynamic_programming[i][j]记录t的前i个字符在s的前j个字符中出现的方案数
// 如果s[j-1]!=t[i-1] 则t[i-1]无法匹配s[j-1],只能做出一种选择就是舍弃s[j-1],选择dp_dynamic_programming[i][j-1]种方案
// 如果s[j-1]==t[i-1] 则t[i-1]可以选择匹配s[j-1],那么就可以选择dp_dynamic_programming[i-1][j-1]中的方案数,也可以选择不匹配,那么就应该选择dp_dynamic_programming[i][j-1]
class Solution {
    public int numDistinct(String s, String t) {
        int m = t.length(), n = s.length();
        int[][] dp_dynamic_programming = new int[m + 1][n + 1];
        
        for (int j = 0; j <= n; j++) {
            dp_dynamic_programming[0][j] = 1;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    dp_dynamic_programming[i][j] = dp_dynamic_programming[i - 1][j - 1] + dp_dynamic_programming[i][j - 1];
                } else {
                    dp_dynamic_programming[i][j] = dp_dynamic_programming[i][j - 1];
                }
            }
        }
        
        return dp_dynamic_programming[m][n];
    }
}
int minInsertions(string s) {
    // need 记录需右括号的需求量
    int res = 0, need = 0;
    
    for (int i = 0; i < s.size(); i++) {
        // 一个左括号对应两个右括号
        if (s[i] == '(') {
            need += 2;
        }
        
        if (s[i] == ')') {
            need--;
        }
    }
    
    return res + need;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

def minInsertions(s: str) -> int:
    # 需要记录需右括号的需求量
    res = 0
    need = 0
    
    for i in range(len(s)):
        # 一个左括号对应两个右括号
        if s[i] == '(':
            need += 2
        
        if s[i] == ')':
            need -= 1
    
    return res + need
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

func minInsertions(s string) int {
    // need 记录需右括号的需求量
    res, need := 0, 0
    
    for i := 0; i < len(s); i++ {
        // 一个左括号对应两个右括号
        if s[i] == '(' {
            need += 2
        }
        
        if s[i] == ')' {
            need--
        }
    }
    
    return res + need
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

// 使用 type annotation 声明函数参数类型
var minInsertions = function(s: string): int {
    // need 记录需右括号的需求量
    int res = 0, need = 0;
    
    for (var i = 0; i < s.length; i++) {
        // 一个左括号对应两个右括号
        if (s[i] == '(') {
            need += 2;
        }
        
        if (s[i] == ')') {
            need--;
        }
    }
    
    return res + need;
};

现在想一想,当 need 为什么值的时候,我们可以确定需要进行插入?

首先,类似第一题,当 need == -1 时,意味着我们遇到一个多余的右括号,显然需要插入一个左括号

比如说当 s = ")",我们肯定需要插入一个左括号让 s = "()",但是由于一个左括号需要两个右括号,所以对右括号的需求量变为 1:

if (s[i] == ')') {
    need--;
    // 说明右括号太多了
    if (need == -1) {
        // 需要插入一个左括号
        res++;
        // 同时,对右括号的需求变为 1
        need = 1;
    }
}

另外,当遇到左括号时,若对右括号的需求量为奇数,需要插入 1 个右括号。因为一个左括号需要两个右括号嘛,右括号的需求必须是偶数,这一点也是本题的难点。

所以遇到左括号时要做如下判断:

if (s[i] == '(') {
    need += 2;
    if (need % 2 == 1) {
        // 插入一个右括号
        res++;
        // 对右括号的需求减一
        need--;
    }
}

综上,我们可以写出正确的代码:

// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

public int minInsertions(String s) {
    int res = 0, need = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            need += 2;
            if (need % 2 == 1) {
                res++;
                need--;
            }
        }
        
        if (s.charAt(i) == ')') {
            need--;
            if (need == -1) {
                res++;
                need = 1;
            }
        }
    }
    
    return res + need;
}
int minInsertions(string s) {
    int res = 0, need = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            need += 2;
            if (need % 2 == 1) {
                res++;
                need--;
            }
        }
        
        if (s[i] == ')') {
            need--;
            if (need == -1) {
                res++;
                need = 1;
            }
        }
    }
    
    return res + need;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

def minInsertions(s: str) -> int:
    res, need = 0, 0
    for i in range(len(s)):
        if s[i] == '(':
            need += 2
            if need % 2 == 1:
                res += 1
                need -= 1
        elif s[i] == ')':
            need -= 1
            if need == -1:
                res += 1
                need = 1
    return res + need
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

func minInsertions(s string) int {
    res, need := 0, 0

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            need += 2
            if need % 2 == 1 {
                res++
                need--
            }
        }
        
        if s[i] == ')' {
            need--
            if need == -1 {
                res++
                need = 1
            }
        }
    }
    
    return res + need
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。

var minInsertions = function(s) {
  let res = 0, need = 0;
  for (let i = 0; i < s.length; i++) {
      if (s[i] === '(') {
          need += 2;
          if (need % 2 === 1) {
              res++;
              need--;
          }
      }
      if (s[i] === ')') {
          need--;
          if (need === -1) {
              res++;
              need = 1;
          }
      }
  }
  return res + need;
}

🥳 代码可视化动画 🥳

综上,三道括号相关的问题就解决了,其实我们前文 有效括号生成算法 也是括号相关的问题,但是使用的回溯算法技巧,和本文的几道题差别还是蛮大的,有兴趣的读者可以去看看。


引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路:

LeetCode 力扣
32. Longest Valid Parentheses 32. 最长有效括号

引用本文的文章

_____________

《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「进群」可加入算法群;回复「全家桶」可下载配套 PDF 和刷题全家桶

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释