Play-Leetcode/0301-Remove-Invalid-Parentheses/cpp-0301/main.cpp at master · interview/Play-Leetcode · GitHub

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/// Source : https://leetcode.com/problems/remove-invalid-parentheses/description/
/// Author : liuyubobobo
/// Time   : 2018-11-02

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// Brute Force
/// Time Complexity: O(2^n)
/// Space Complexity: O(n)
class Solution {

private:
    int n;
    int maxlen;

public:
    vector<string> removeInvalidParentheses(string s) {

        n = s.size();
        maxlen = 0;

        unordered_set<string> res;
        dfs(s, 0, 0, "", res);
        return vector<string>(res.begin(), res.end());
    }

private:
    void dfs(const string& s, int index, int left, const string& cur,
             unordered_set<string>& res){

        if(index == n){
            if(left == 0){
                if(cur.size() > maxlen){
                    res.clear();
                    maxlen = cur.size();
                }

                if(cur.size() == maxlen)
                    res.insert(cur);
            }
            return;
        }

        if(s[index] != '(' && s[index] != ')')
            dfs(s, index + 1, left, cur + s[index], res);
        else if(s[index] == '('){
            dfs(s, index + 1, left + 1, cur + s[index], res);
            if(cur.size() + n - (index + 1) >= maxlen)
                dfs(s, index + 1, left, cur, res);
        }
        else{
            if(left > 0)
                dfs(s, index + 1, left - 1, cur + s[index], res);
            if(cur.size() + n - (index + 1) >= maxlen)
                dfs(s, index + 1, left, cur, res);
        }
    }
};


void print_vec(const vector<string>& vec){

    cout << vec.size() << " : ";
    for(const string& e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    string s1 = "()())()";
    print_vec(Solution().removeInvalidParentheses(s1));
    // 6
    // (())() ()()()

    string s2 = "(a)())()";
    print_vec(Solution().removeInvalidParentheses(s2));
    // 7
    // (a())() (a)()()

    string s3 = ")(";
    print_vec(Solution().removeInvalidParentheses(s3));
    // 0

    string s4 = "n";
    print_vec(Solution().removeInvalidParentheses(s4));
    // 1
    // n

    string s5 = "x(";
    print_vec(Solution().removeInvalidParentheses(s5));
    // 1
    // x

    string s6 = "((";
    print_vec(Solution().removeInvalidParentheses(s6));
    // 0


    return 0;
}