leetcode-301-Remove Invalid Parentheses

Posted on | In , | |
Words count in article: 252 | Reading time ≈ 1

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 ).

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]
Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
Example 3:

Input: ")("
Output: [""]

  • 从左到右检查多余的“）”，多了就要删除前面的一个“）”（条件是：不连续的就肯定可以删，连续的“）”只删除第一个，因为是一样的效果）
  • 做完从左到右之后做一次从右到左，就是最后结果
  • 只要一轮，不要重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void DFS(string s, char ch, int last)
    {
        for(int i = 0, cnt = 0; i < s.size(); i++)
        {
            if(s[i]=='('||s[i]==')') s[i]==ch?cnt++:cnt--;
            if(cnt <= 0) continue;
            for(int j = last; j <= i; j++)
            {
                if(s[j] == ch && (j ==last || s[j-1]!= ch))
                    DFS(s.substr(0, j)+s.substr(j+1), ch, j);
            }
            return;
        }
        reverse(s.begin(), s.end());
        if(ch == ')') return DFS(s, '(', 0);
        ans.push_back(s);
    }
    
    vector<string> removeInvalidParentheses(string s) {
        DFS(s, ')', 0);
        return ans;
    }
private:
    vector<string> ans;
};
Donate? comment?