LeetCode-301. Remove Invalid Parentheses
LeetCode-301. Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Example 1:
Input: "()())()"Output: ["()()()", "(())()"]
Example 2:
Input: "(a)())()"Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")("Output: [""]
题解:
使用dfs查找,先遍历字符串找出最少需要删除的左括号和右括号个数,然后dfs删除。
class Solution {public: bool isValid(string s) { int cnt = 0; for (int i = 0; i < s.length(); i++) { if (s[i] == '(') { cnt++; } else if (s[i] == ')') { cnt--; if (cnt < 0) { return false; } } } return cnt == 0; } void dfs(int k, string &s, unordered_set
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~