网站未备案怎么访问,免费建网站的步骤,网站建设与维护的卷子,哈尔滨优化seo外包公司文章目录1. 题目2. 解题1. 题目
删除最小数量的无效括号#xff0c;使得输入的字符串有效#xff0c;返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: ()())()
输出: [()()(), (())()]示例 2:
输入:…
文章目录1. 题目2. 解题1. 题目
删除最小数量的无效括号使得输入的字符串有效返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: ()())()
输出: [()()(), (())()]示例 2:
输入: (a)())()
输出: [(a)()(), (a())()]示例 3:
输入: )(
输出: []来源力扣LeetCode 链接https://leetcode-cn.com/problems/remove-invalid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
直接回溯注意剪枝
class Solution {unordered_setstring ans;//去重int mindel INT_MAX;
public:vectorstring removeInvalidParentheses(string s) {int l 0, r 0, del 0;string t;dfs(s,0,t,l,r,del);return vectorstring(ans.begin(), ans.end());}void dfs(string s, int idx, string t, int l, int r, int del){if(del mindel)//删的多了没意义了return;if(idx s.size()){if(lr del mindel)//左右括号数量要一样多{mindel del;ans.clear();ans.insert(t);}else if(lr del mindel)ans.insert(t);return;}if(s[idx]!( s[idx]!))//不是括号加上跳过return dfs(s, idx1, ts[idx], l, r, del);if(s[idx]() l;else if(s[idx] )) r;if(l r)//左括号在过程中一直右括号dfs(s, idx1, ts[idx], l, r, del);//不删除if(s[idx]() l--;//回溯else if(s[idx] )) r--;//回溯if(l r)dfs(s, idx1,t, l, r, del1);//删除}
};152 ms 22 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
