學算法認準 labuladong
東哥帶你手把手撕力扣😏
讀完本文，你可以去力扣解決如下問題：
20.有效的括號（Easy）
921.使括號有效的最小插入（Medium）
1541.平衡括號串的最少插入（Medium）
對括號的合法性判斷多次在筆試中出現，現實中也很常見，比如說我們寫的代碼，編輯器會檢查括號是否正確閉合。而且我們的代碼可能會包含三種括號[](){}，判斷起來有一點難度。
來看一看力扣第 20 題「有效的括號」，輸入一個字符串，其中包含[](){}六種括號，請你判斷這個字符串組成的括號是否合法。
舉幾個例子：
Input: "()[]{}"
Output: true
Input: "([)]"
Output: false
Input: "{[]}"
Output: true
解決這個問題之前，我們先降低難度，思考一下，如果只有一種括號()，應該如何判斷字符串組成的括號是否合法呢？
假設字符串中只有圓括號，如果想讓括號字符串合法，那麼必須做到：
每個右括號)的左邊必須有一個左括號(和它匹配。
比如說字符串()))((中，中間的兩個右括號左邊就沒有左括號匹配，所以這個括號組合是不合法的。
那麼根據這個思路，我們可以寫出算法：
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;
}
如果只有圓括號，這樣就能正確判斷合法性。對於三種括號的情況，我一開始想模仿這個思路，定義三個變量left1，left2，left3分別處理每種括號，雖然要多寫不少 if else 分支，但是似乎可以解決問題。
但實際上直接照搬這種思路是不行的，比如說只有一個括號的情況下(())是合法的，但是多種括號的情況下，[(])顯然是不合法的。
僅僅記錄每種左括號出現的次數已經不能做出正確判斷了，我們要加大存儲的信息量，可以利用棧來模仿類似的思路。棧是一種先進後出的數據結構，處理括號問題的時候尤其有用。
我們這道題就用一個名為left的棧代替之前思路中的left變量，遇到左括號就入棧，遇到右括號就去棧中尋找最近的左括號，看是否匹配：
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 '[';
}
接下來講另外兩個常見的問題，如何通過最小的插入次數將括號變成合法的？
平衡括號串（一）先來個簡單的，力扣第 921 題「使括號有效的最少添加」：
給你輸入一個字符串s，你可以在其中的任意位置插入左括號(或者右括號)，請問你最少需要幾次插入才能使得s變成一個合法的括號串？
比如說輸入s = "())("，算法應該返回 2，因為我們至少需要插入兩次把s變成"(())()"，這樣每個左括號都有一個右括號匹配，s是一個合法的括號串。
這其實和前文的判斷括號合法性非常類似，我們直接看代碼：
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;
}
這段代碼就是最終解法，核心思路是以左括號為基準，通過維護對右括號的需求數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變量：
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;
}
現在想一想，當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--;
}
}
綜上，我們可以寫出正確的代碼：
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;
}
綜上，三道括號相關的問題就解決了，其實我們前文 合法括號生成算法 也是括號相關的問題，但是使用的回溯算法技巧，和本文的幾道題差別還是蠻大的，有興趣的讀者可以去看看。