leetcode 301. 删除无效的括号 困难

给你一个由若干括号和字母组成的字符串s删除最小数量的无效括号使得输入的字符串有效。返回所有可能的结果。答案可以按任意顺序返回。示例 1输入s ()())()输出[(())(),()()()]示例 2输入s (a)())()输出[(a())(),(a)()()]示例 3输入s )(输出[]提示1 s.length 25s由小写英文字母以及括号(和)组成s中至多含20个括号分析BFS 的核心是按“删除括号的数量”一层一层搜索。把原字符串作为第 0 层。如果它不合法就枚举删除其中一个括号得到第 1 层的所有字符串如果第 1 层仍然没有合法结果就继续删除一个括号得到第 2 层。由于 BFS 是按删除次数递增搜索的所以第一次出现合法字符串时这一层对应的删除次数一定是最少的。此时收集这一层所有合法字符串直接结束搜索不需要继续往下一层。搜索过程中要使用集合进行去重避免同一个字符串被重复加入队列。连续相同的括号也可以跳过重复删除的位置进一步减少搜索量。判断字符串是否合法时从左到右扫描遇到(计数加一遇到)计数减一。如果中途计数小于 0说明出现了无法匹配的右括号最后计数为 0则说明括号完全匹配。因此整体思路就是原字符串 → 删除 1 个括号的所有情况 → 删除 2 个括号的所有情况 → ……第一次找到合法字符串的那一层就是最终答案。class Solution { public: vectorstring removeInvalidParentheses(string s) { vectorstringans; queuestringq;q.push(s); unordered_setstringvisited;visited.insert(s); bool foundfalse; while(!q.empty()) { int sizeq.size(); for(int k0;ksize;k) { string curq.front();q.pop(); if(isValid(cur)) ans.push_back(cur),foundtrue; if(found)continue; for(int i0;icur.size();i) { if(cur[i]!(cur[i]!))continue; if(i0cur[i]cur[i-1])continue; string nextcur.substr(0,i)cur.substr(i1); if(!visited.count(next)) visited.insert(next),q.push(next); } } if(found)break; } return ans; } bool isValid(const string s) { int cnt0; for (int i0;s[i];i) { char cs[i]; if(c()cnt; else if (c )) { cnt--; if(cnt0)return false; } } return cnt0; } };