Graph/301_Remove_Invalid_parentheses.cpp at master · Brajmohank1/Graph · 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
/*
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.


Example 1:

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

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]


*/


class Solution {
public:

    bool isValid(string str){

        int count = 0;
        int n = str.size();
        for(int i = 0 ; i < n ; i++){
            if(str[i] == '(') count++;
            if(str[i] == ')') count--;

            if(count < 0)
                return false;
        }

        return count == 0;

    }
    vector<string> removeInvalidParentheses(string s) {

        vector<string> res;
        queue<string> q;
        unordered_set<string> brajset;
        int len = INT_MAX;
        q.push(s);

        while(!q.empty()){


            string temp = q.front() ;
            q.pop();
             if(len != INT_MAX && len != temp.size())
                    break;

            if(isValid(temp)){
                len = temp.size();
                res.push_back(temp);


                continue;

            }

            for(int i = 0 ; i < temp.size() ; i++){
                if(temp[i] == '(' || temp[i] == ')')
                {  string left = temp.substr(0 , i) + temp.substr(i + 1 );
                  if(brajset.find(left) == brajset.end())
                      q.push(left);
                 brajset.insert(left);

                }
            }


        }

        if(res.size() == 0)
            res.push_back(" ");

        return res;

    }
};