如何解决括号相关的问题

1541. 平衡括号字符串的最少插入次数 https://leetcode.cn/problems/minimum-insertions-to-balance-a-parentheses-string

1541. Minimum Insertions to Balance a Parentheses String https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string

20. 有效的括号 https://leetcode.cn/problems/valid-parentheses

20. Valid Parentheses https://leetcode.com/problems/valid-parentheses

921. 使括号有效的最少添加 https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid

921. Minimum Add to Make Parentheses Valid https://leetcode.com/problems/minimum-add-to-make-parentheses-valid

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

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

LeetCode	Difficulty
1541. Minimum Insertions to Balance a Parentheses String	🟠
20. Valid Parentheses	🟢
921. Minimum Add to Make Parentheses Valid	🟠

Prerequisites

Before reading this article, you should learn:

• Principles of Queues/Stacks

Valid Parentheses String

The validity of parentheses is a common topic in written exams and real-life scenarios. For example, when we write code, the editor checks if the parentheses are correctly closed. Moreover, our code may contain three types of parentheses: [](){}, which adds a bit of complexity to the validation.

Let's look at LeetCode problem #20 "Valid Parentheses". Given a string containing [](){} six types of parentheses, you need to determine if the string's parentheses are valid:

20. Valid Parentheses | 力扣 | LeetCode |

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Before solving this problem, let's simplify it. Think about how to determine if a string of parentheses is valid if it only contains one type of parentheses: ().

Assume the string only contains round parentheses. For the parentheses string to be valid, the following must be true:

Each right parenthesis ) must have a matching left parenthesis ( on its left.

For example, in the string ()))((, the two right parentheses in the middle do not have matching left parentheses on their left, making this combination invalid.

Based on this idea, we can write the algorithm:

java 🟢

boolean isValid(String str) {
    // number of left parentheses to be matched
    int left = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == '(') {
            left++;
        } else {
            // encounter a right parenthesis
            left--;
        }

        // too many right parentheses
        if (left == -1)
            return false;
    }
    // whether all left parentheses have been matched
    return left == 0;
}

cpp 🤖

bool isValid(std::string str) {
    // number of left parentheses to be matched
    int left = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            left++;
        } else {
            // encounter a right parenthesis
            left--;
        }

        // too many right parentheses
        if (left == -1)
            return false;
    }
    // whether all left parentheses have been matched
    return left == 0;
}

python 🤖

def isValid(str):
    # number of left parentheses to be matched
    left = 0
    for i in range(len(str)):
        if str[i] == '(':
            left += 1
        else:
            # encounter a right parenthesis
            left -= 1
        # too many right parentheses
        if left == -1:
            return False
    # whether all left parentheses have been matched
    return left == 0

go 🤖

func isValid(str string) bool {
    // number of left parentheses to be matched
    var left int
    for i := 0; i < len(str); i++ {
        if str[i] == '(' {
            left++
        } else {
            // encounter a right parenthesis
            left--
        }

        // too many right parentheses
        if left == -1 {
            return false
        }
    }
    // whether all left parentheses have been matched
    return left == 0
}

javascript 🤖

var isValid = function(str) {
    // the number of left parentheses to be matched
    var left = 0;
    for (var i = 0; i < str.length; i++) {
        if (str.charAt(i) == '(') {
            left++;
        } else {
            // encounter a right parenthesis
            left--;
        }

        // too many right parentheses
        if (left == -1)
            return false;
    }
    // whether all left parentheses have been matched
    return left == 0;
}

If there are only parentheses, this method can correctly determine validity. For the case with three types of brackets, I initially thought to模仿 this approach by defining three variables left1, left2, left3 to handle each type of bracket. Although it requires writing more if-else branches, it seemed to solve the problem.

However, directly copying this approach doesn't work. For example, (()) is valid with only one type of bracket, but with multiple types, [(]) is clearly invalid.

Simply recording the count of each left bracket is no longer sufficient for correct judgment. We need to increase the amount of stored information. We can use a stack to mimic a similar approach. A stack is a Last-In-First-Out (LIFO) data structure, which is especially useful for handling bracket problems.

In this problem, we use a stack named left to replace the left variable from the previous approach. When we encounter a left bracket, we push it onto the stack. When we encounter a right bracket, we look for the nearest left bracket in the stack to see if it matches:

java 🟢

class Solution {
    public boolean isValid(String str) {
        Stack<Character> left = new Stack<>();
        for (char c : str.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                left.push(c);
            } else {
                // character c is a right parenthesis
                if (!left.isEmpty() && leftOf(c) == left.peek()) {
                    left.pop();
                } else {
                    // does not match the nearest left parenthesis
                    return false;
                }
            }
        }
        // whether all left parentheses have been matched
        return left.isEmpty();
    }

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

cpp 🤖

class Solution {
public:
    bool isValid(string str) {
        stack<char> left;
        for (char c : str) {
            if (c == '(' || c == '{' || c == '[') {
                left.push(c);
            } else {
                // character c is a right parenthesis
                if (!left.empty() && leftOf(c) == left.top()) {
                    left.pop();
                } else {
                    // does not match the nearest left parenthesis
                    return false;
                }
            }
        }
        // whether all left parentheses have been matched
        return left.empty();
    }

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

python 🤖

class Solution:
    def isValid(self, str: str) -> bool:
        left = []
        for c in str:
            if c in '([{':
                left.append(c)
            # character c is a right parenthesis
            else:
                if left and self.leftOf(c) == left[-1]:
                    left.pop()
                else:
                    # does not match the most recent left parenthesis
                    return False
        # whether all left parentheses have been matched
        return not left

    def leftOf(self, c: str) -> str:
        if c == '}': return '{'
        if c == ')': return '('
        return '['

go 🤖

func isValid(str string) bool {
    var left []rune
    for _, c := range str {
        if c == '(' || c == '{' || c == '[' {
            left = append(left, c)
        } else {
            // character c is a right parenthesis
            if len(left) > 0 && leftOf(c) == left[len(left)-1] {
                left = left[:len(left)-1]
            } else {
                // does not match the nearest left parenthesis
                return false
            }
        }
    }
    // whether all left parentheses are matched
    return len(left) == 0
}

func leftOf(c rune) rune {
    if c == '}' {
        return '{'
    }
    if c == ')' {
        return '('
    }
    return '['
}

javascript 🤖

var isValid = function(str) {
    let left = [];
    for (let c of str) {
        if (c === '(' || c === '{' || c === '[') {
            left.push(c);
        } else {
            // character c is a right parenthesis
            if (left.length > 0 && leftOf(c) === left[left.length - 1]) {
                left.pop();
            } else {
                // does not match the nearest left parenthesis
                return false;
            }
        }
    }
    // whether all left parentheses are matched
    return left.length === 0;
}

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

Next, let's discuss two common problems: How can you make brackets valid with the minimum number of insertions?

Balanced Bracket String (Part 1)

Let's start with a simple one, LeetCode problem #921 "Minimum Add to Make Parentheses Valid":

Given a string s, you can insert a left parenthesis ( or a right parenthesis ) at any position. How many insertions do you need at minimum to make s a valid bracket string?

For example, if the input is s = "())(", the algorithm should return 2. This is because we need at least two insertions to transform s into "(())()". In this form, every left parenthesis has a matching right parenthesis, making s a valid bracket string.

This problem is quite similar to the previous one about checking bracket validity. Let's directly look at the code:

java 🟢

class Solution {
    public int minAddToMakeValid(String s) {
        // res records the number of insertions
        int res = 0;
        // need variable records the demand for right parentheses
        int need = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // increase the demand for right parentheses by 1
                need++;
            }

            if (s.charAt(i) == ')') {
                // decrease the demand for right parentheses by 1
                need--;

                if (need == -1) {
                    need = 0;
                    // need to insert a left parenthesis
                    res++;
                }
            }
        }

        return res + need;
    }
}

cpp 🤖

class Solution {
public:
    int minAddToMakeValid(string s) {
        // res records the number of insertions
        int res = 0;
        // need variable records the demand for right parentheses
        int need = 0;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                // the demand for right parentheses + 1
                need++;
            }

            if (s[i] == ')') {
                // the demand for right parentheses - 1
                need--;

                if (need == -1) {
                    need = 0;
                    // need to insert a left parenthesis
                    res++;
                }
            }
        }

        return res + need;
    }
};

python 🤖

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        # res records the number of insertions
        res = 0
        # need variable records the demand for right parentheses
        need = 0

        for i in range(len(s)):
            if s[i] == '(':
                # increase the demand for right parentheses by 1
                need+=1

            if s[i] == ')':
                # decrease the demand for right parentheses by 1
                need-=1
            
                if need == -1:
                    need = 0
                    # need to insert a left parenthesis
                    res+=1
                   
        return res + need

go 🤖

func minAddToMakeValid(s string) int {
    // res records the number of insertions
    res := 0
    // need variable records the demand for right parentheses
    need := 0

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            // increase the demand for right parentheses by 1
            need++
        }

        if s[i] == ')' {
            // decrease the demand for right parentheses by 1
            need--

            if need == -1 {
                need = 0
                // need to insert a left parenthesis
                res++
            }
        }
    }

    return res + need
}

javascript 🤖

var minAddToMakeValid = function(s){
    // res records the number of insertions
    let res = 0;
    // need variable records the demand for right parentheses
    let need = 0;

    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) === '(') {
            // the demand for right parentheses + 1
            need++;
        }

        if (s.charAt(i) === ')') {
            // the demand for right parentheses - 1
            need--;

            if (need === -1) {
                need = 0;
                // need to insert a left parenthesis
                res++;
            }
        }
    }

    return res + need;
};

This code is the final solution. The core idea is to use left parentheses as a reference and maintain the required number of right parentheses need to calculate the minimum number of insertions. There are two important points to note:

1. What does need == -1 mean?

Since need-- only occurs when encountering a right parenthesis ), need == -1 means there are too many right parentheses, so a left parenthesis needs to be inserted.

For example, in the case of s = "))", 2 left parentheses need to be inserted to make s into "()()", which is a valid parentheses string.

2. Why does the algorithm return res + need?

Because res records the number of left parentheses inserted, and need records the demand for right parentheses. When the for loop ends, if need is not 0, it means there are not enough right parentheses, and more need to be inserted.

For example, in the case of s = "))(", after inserting 2 left parentheses, 1 right parenthesis also needs to be inserted to make s into "()()()", which is a valid parentheses string.

This is the approach for this problem. Next, let's look at an advanced problem: what issues arise if left and right parentheses are not paired 1:1?

Balanced Parentheses (Part 2)

This is LeetCode problem #1541, "Minimum Insertions to Balance a Parentheses String":

Now assume that 1 left parenthesis needs to be matched with 2 right parentheses to form a valid parentheses combination. Given a parentheses string s, how do you calculate the minimum number of insertions needed to make s valid?

The core idea remains the same: use a need variable to record the required number of right parentheses and determine whether insertions are needed based on changes in need.

First, we correctly maintain the need variable as per the previous approach:

java 🟢

int minInsertions(String s) {
    // need records the demand for right parentheses
    int res = 0, need = 0;
    for (int i = 0; i < s.length(); i++) {
        // one left parenthesis corresponds to two right parentheses
        if (s.charAt(i) == '(') {
            need += 2;
        }

        if (s.charAt(i) == ')') {
            need--;
        }
    }
    return res + need;
}

cpp 🤖

int minInsertions(std::string s) {
    // need records the demand for right parentheses
    int res = 0, need = 0;
    for (int i = 0; i < s.size(); i++) {
        // one left parenthesis corresponds to two right parentheses
        if (s[i] == '(') {
            need += 2;
        }

        if (s[i] == ')') {
            need--;
        }
    }
    return res + need;
}

python 🤖

def minInsertions(s: str) -> int: 
    # need records the demand for right parentheses
    res = 0 
    need = 0 
    for i in range(len(s)):
        # one left parenthesis corresponds to two right parentheses
        if s[i] == '(': 
            need += 2 

        if s[i] == ')': 
            need -= 1 

    return res + need

go 🤖

func minInsertions(s string) int {
    // need records the demand for right parentheses
    var res int = 0
    var need int = 0
    for i := 0; i < len(s); i++ {
        // one left parenthesis corresponds to two right parentheses
        if string(s[i]) == "(" {
            need += 2
        }
        if string(s[i]) == ")" {
            need--
        }
    }
    return res + need
}

javascript 🤖

var minInsertions = function(s) {
    // need records the demand for right parentheses
    var res = 0, need = 0;
    for (var i = 0; i < s.length; i++) {
        // one left parenthesis corresponds to two right parentheses
        if (s.charAt(i) === '(') {
            need += 2;
        }

        if (s.charAt(i) === ')') {
            need--;
        }
    }
    return res + need;
}

Now think about it, for what value of need can we determine that an insertion is necessary?

Firstly, similar to the first question, when need == -1, it means we have encountered an extra right parenthesis, which obviously requires the insertion of a left parenthesis.

For example, when s = ")", we definitely need to insert a left parenthesis to make s = "()". However, since one left parenthesis requires two right parentheses, the demand for right parentheses becomes 1:

if (s[i] == ')') {
    need--;
    // it means there are too many right parentheses
    if (need == -1) {
        // need to insert a left parenthesis
        res++;
        // at the same time, the need for right parentheses becomes 1
        need = 1;
    }
}

Additionally, when encountering a left parenthesis, if the required number of right parentheses is odd, one right parenthesis needs to be inserted. This is because one left parenthesis needs two right parentheses, so the demand for right parentheses must be even, which is also a key challenge in this problem.

Therefore, when encountering a left parenthesis, the following judgment should be made:

if (s[i] == '(') {
    need += 2;
    if (need % 2 == 1) {
        // insert a right parenthesis
        res++;
        // decrease the need for one right parenthesis
        need--;
    }
}

In summary, we can write the correct code:

java 🟢

class Solution {
    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;
    }
}

cpp 🤖

class Solution {
public:
    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 🤖

class Solution:
    def minInsertions(self, s: str) -> int:
        res = 0 
        need = 0
        for i in range(len(s)):
            if s[i] == '(':
                need += 2
                if need % 2 == 1:
                    res += 1
                    need -= 1
            if s[i] == ')':
                need -= 1
                if need == -1:
                    res += 1
                    need = 1
        return res + need

go 🤖

func minInsertions(s string) int {
    res := 0
    need := 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 🤖

var minInsertions = function(s) {
    let res = 0, need = 0;
    for (let 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;
}

In summary, the three bracket-related problems have been solved. Actually, in our previous article Valid Parentheses Generation Algorithm, we also dealt with bracket-related problems, but we used backtracking techniques, which are quite different from the methods used in this article. Interested readers can check it out.

---

引用本文的题目

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

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

---