本文涉及知识点
字符串 括号匹配 广度优先
LeetCode301 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = “()())()”
输出：[“(())()”,“()()()”]
示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,“(a)()()”]
示例 3：
输入：s = “)(”
输出：[“”]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号
预备知识
合法括号的定义：
一，()是合法括号。
二,A和B是合法括号。则AB也是合法括号。A=() B = () 则()()是合法括号。
三，(A)是合法括号。A=()()，则(()())是合法括号。
性质：
num=0,从左到右解析括号，遇到(++，遇到)–。性质一：num任何时候都不能为负。性质二：num最终必须为0。
定义是性质的充分条件容易证明，下面来证明必要条件。
令num1[i]是s[0,i]的num之和。
num1[j]不为0且大于等于0 → \rightarrow→ num1[j]大于等于1
移除（后，nums1[j]全部-- 任然符合性质一
s[i]合法→ \rightarrow→ num1[i]==0 → \rightarrow→ num1[i-1]为1
移除(后，变成0，符合性质二。
不断拆分，知道s的长度为2为止。
广度优先
初始字符为空。
hasAdd 记录增加了多少字符。
num 记录字符的权值和，(为1，)为-1。
删除）时，无需判断，因为只会让其它)的num变大或不变。
删除)时，需要判断，因为可能让某个)的num变成负数。
代码
核心代码
class Solution { public: vector<string> removeInvalidParentheses(string s) { int num = 0; unordered_set<string> pre = { "" }; int iDelLeft=0,iDelRight = 0; for (int i = 0; ; i++) { unordered_set<string> dp; const int hasAdd = i - iDelLeft -iDelRight; if (num < 0) {//删除一个右括号 iDelRight++; num++; for (const string& str : pre) { for (int j = 0; j < str.length(); j++) { if (')' == str[j]) { dp.emplace(str.substr(0, j) + str.substr(j + 1)); } } } } else if (hasAdd < s.length()) { if ('(' == s[hasAdd]) { num++; } else if (')' == s[hasAdd]) { num--; } for (const string& str : pre) { dp.emplace(str + s[hasAdd]); } } else { if (num > 0) {//删除一个左括号 num--; iDelLeft++; for (const string& str : pre) { for (int j = 0; j < str.length(); j++) { if ('(' == str[j]) { dp.emplace(str.substr(0, j) + str.substr(j + 1)); } } } } else { break; } } dp.swap(pre); } vector<string> vRet; for (const string& str : pre) { if (IsVilid(str)) { vRet.emplace_back(str); } } return vRet; } bool IsVilid(const string& str) { int num = 0; for (const auto& ch : str) { if ('(' == ch) { num++; } else if (')' == ch) { num--; } if (num < 0) { return false; } } return 0 == num; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string s; { Solution sln; s = ")()("; auto res = sln.removeInvalidParentheses(s); Assert({ "()" }, res); } { Solution sln; s = ")("; auto res = sln.removeInvalidParentheses(s); Assert({ "" }, res); } { Solution sln; s = "()())()"; auto res = sln.removeInvalidParentheses(s); Assert({ "(())()", "()()()" }, res); } { Solution sln; s = "(a)())()"; auto res = sln.removeInvalidParentheses(s); Assert({ "(a())()","(a)()()" }, res); } }
简洁版
class CBracket { public: static int ToInt(const char& ch) { if ('(' == ch) { return 1; } return (')' == ch) ? -1 : 0; } static bool IsVilid(const string& str) { int num = 0; for (const auto& ch : str) { num += ToInt(ch); if (num < 0) { return false; } } return 0 == num; } }; class Solution { public: vector<string> removeInvalidParentheses(string s) { int num = 0; unordered_set<string> pre = { "" }; int iHasAdd = 0; while(true) { unordered_set<string> dp; auto Del = [&pre,&dp](char ch) { for (const string& str : pre) { for (int j = 0; j < str.length(); j++) { if (ch == str[j]) { dp.emplace(str.substr(0, j) + str.substr(j + 1)); } } } }; if (num < 0) {//删除一个右括号 num++; Del(')'); } else if (iHasAdd < s.length()) { num += CBracket::ToInt(s[iHasAdd]); for (const string& str : pre) { dp.emplace(str + s[iHasAdd]); } iHasAdd++; } else { if (num > 0) {//删除一个左括号 num--; Del('('); } else { break; } } dp.swap(pre); } vector<string> vRet; for (const string& str : pre) { if (CBracket::IsVilid(str)) { vRet.emplace_back(str); } } return vRet; } };
2023年4月版
class Solution { public: vector removeInvalidParentheses(string s) { int iNeedDelLeft = 0, iNeedDelRight = 0; { for (int i = 0; i < s.length(); i++) { const char& ch = s[i]; if ((‘(’ == ch) || (‘)’ == ch)) { vRangeIndexs.emplace_back(i); } if (‘(’ == ch) { iNeedDelLeft++; } if (‘)’ == ch) { if (iNeedDelLeft > 0) { iNeedDelLeft–; } else { iNeedDelRight++; } } } } m_iMaskNum = 1 << vRangeIndexs.size(); auto Is = [&](const int iMask) { int iNum = 0; for (int j = 0; j < vRangeIndexs.size(); j++) { if (iMask & (1 << j)) {//此位置删除 continue; } const char& ch = s[vRangeIndexs[j]]; if (‘(’ == ch) { iNum++; } if (‘)’ == ch) { iNum–; } if (iNum < 0) { return false; } } return 0 == iNum; }; std::unordered_set setRet; for (int iMask = 0; iMask < m_iMaskNum; iMask++) { if (bitcount(iMask) != (iNeedDelLeft + iNeedDelRight)) { continue; } if (!Is(iMask)) { continue; } std::vector indexs,subIndexs; for (int i = 0; i < s.length(); i++) { indexs.emplace_back(i); } for (int j = 0; j < vRangeIndexs.size(); j++) { if (iMask & (1 << j)) {//此位置删除 subIndexs.emplace_back(vRangeIndexs[j]); } } vector v; string str; std::set_difference(indexs.begin(), indexs.end(), subIndexs.begin(), subIndexs.end(), std::back_inserter(v)); for (const auto& tmp : v) { str += s[tmp]; } setRet.emplace(str); } return vector(setRet.begin(), setRet.end()); } int m_iMaskNum; vector vRangeIndexs; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
