Clean C++ 0ms solution with comments


  • 1

    Idea is to search twice the string (left to right, and right to left), and get rid of all necessary chars.

    class Solution {
    private:
        vector<string> ans;
        
        void gen(string s, int start, int lbound, char inc, char dec) { // search from start, delete until lbound
            int cnt = 0;
            for (int i = start; i < s.length(); i++) {
                cnt += s[i] == inc ? 1 : s[i] == dec ? -1 : 0;
                
                if (cnt == -1) {                                    // if got extra dec, delete all possible positions
                    int j = i;
                    while (lbound <= j) {
                        if ((j == lbound || s[j - 1] != s[j]) && s[j] == dec) { // skip duplicates, delete until lbound
                            gen(s.substr(0, j) + s.substr(j + 1), i, j, inc, dec);
                        }
                        j--;
                    }
                    return;
                }
            }
            
            reverse(s.begin(), s.end());
            if (inc == '(') {                           // if it's first round, search the reverse string again
                gen(s, 0, 0, dec, inc);
            } else {
                ans.push_back(s);                       // if it's second round, it's a valid path, add to ans
            }
        }
        
    public:
        vector<string> removeInvalidParentheses(string s) {
            gen(s, 0, 0, '(', ')');
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.