力扣 LeetCode 301. 删除无效的括号 - 力扣（LeetCode） 301. 删除无效的括号 - 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。   示例 1： 输入：s = "()())()" 输出：["(())()","()()()"] 示例 2： 输入：s = "(a)())()" 输出：["(a())()","(a)()()"] 示例 3： 输入：s = ")(" 输出：[""]   提示： * 1 <= s.length... 思路 咱用的是 DFS，DFS 回溯思路还是很自然的，递归过程中要维护剩余操作数和括号平衡情况的状态。这个移除的最小操作数我们是可以直接算出来的， 昨天那道题 已经做了铺垫。 递归终点是扫描的下标到达 s 末端，或者右括号比左括号多的时候。前者发生时就可以判断括号串是否平衡以及操作数是否都用上了。 值得注意的是可能产生重复的结果，还需要去重。 这题好像还有效率更高的 BFS 解法，看佬友们的发挥了 代码 class Solution { public: vector<string> removeInvalidParentheses(string s) { // 很容易能算出要删除的最小数量是多少 int left=0; int right=0; for(char c:s){ if(c=='('){ left++; }else if(c==')'){ if(left>0){ left--; }else{ right++; } } } // left+right 就是最小数量 string temp; vector<string> res; unordered_set<string> sSet; // 在 i 下标，还剩 ops 次移除，balance 为 0 时表示括号当前平衡 auto dfs=[&](this auto&& self,int i,int ops,int balance) -> void { if(balance<0){ // 右括号过多，不符合 return; } if(i>=s.size()){ if(balance==0&&ops==0){ // 平衡了且操作全用了 if(sSet.count(temp)==0){ // 还要去重 res.emplace_back(temp); sSet.insert(temp); } } return; } if(s[i]>='a'&&s[i]<='z'){ // 是字母 temp.push_back(s[i]); self(i+1,ops,balance); temp.pop_back(); }else{ if(ops>0){ // 还有操作空间，就看看移除这个括号能不能得到有效的 self(i+1,ops-1,balance); } // 接下来是不移除的情况 if(s[i]=='('){ balance++; }else{ balance--; } temp.push_back(s[i]); self(i+1,ops,balance); temp.pop_back(); } }; dfs(0,left+right,0); return res; } }; 1 个帖子 - 1 位参与者 阅读完整话题

  • 情报分类：综合情报
  • 分类依据：内容未命中明确的垂直分类规则，归入综合情报
  • 信息来源：服务器 / LINUX DO - 最新话题
  • 发布时间：2026/10/7 10:05:10