題目描述

給你一個(gè)由若干括號(hào)和字母組成的字符串 s ，刪除最小數(shù)量的無(wú)效括號(hào)，使得輸入的字符串有效。

返回所有可能的結(jié)果。答案可以按 任意順序 返回。

示例 1：
輸入：s = “()())()”
輸出：["(())()","()()()"]

示例 2：
輸入：s = “(a)())()”
輸出：["(a())()","(a)()()"]

示例 3：
輸入：s = “)(”
輸出：[""]

提示：
1 <= s.length <= 25
s 由小寫英文字母以及括號(hào) ‘(’ 和 ‘)’ 組成
s 中至多含 20 個(gè)括號(hào)

---

簡(jiǎn)單的DFS回溯，每個(gè)括號(hào)有刪和不刪兩種狀態(tài)，遍歷即可， 如想優(yōu)化可加剪枝。

---

class Solution { private: vector<string> ans;unordered_set<string>un; public:// 這里判斷合法時(shí)，并不僅僅統(tǒng)計(jì)左右括號(hào)數(shù)是否相等，而是統(tǒng)計(jì)左括號(hào)在左側(cè)而右括號(hào)在右側(cè)bool judge(string str) {int count = 0;for (char c : str) {if (c == '(') {count++;} else if (c == ')') {count--;if (count < 0) {return false;}}}return count == 0;}vector<string> removeInvalidParentheses(string s) {int left = 0, right = 0;// 找出不合法的左右括號(hào)數(shù)for (int i = 0; i < s.length(); i++) {if (s[i] == '(') {left++;} else if (s[i] == ')') {if (left > 0) left--;else right++;}}// 進(jìn)行回溯dfs(s, 0, left, right);for(auto i : un) {ans.push_back(i);}return ans;}void dfs(string s, int index, int left, int right) {// 終止條件if (left == 0 && right == 0) {if (judge(s)) {un.insert(s);return;}}int len = s.length();for (int i = index; i < len; i++) {// 刪除左括號(hào)if (left > 0 && s[i] == '(') {dfs(s.substr(0, i) + s.substr(i + 1, len - i - 1), i, left -1, right);}// 刪除右括號(hào)if (right > 0 && s[i] == ')') {dfs(s.substr(0, i) + s.substr(i + 1, len - i - 1), i, left, right - 1);}}} };

總結(jié)

以上是生活随笔為你收集整理的Leecode 301. 删除无效的括号——Leecode每日一题系列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。