LOL O(2^n) but pass!


  • 0
    0
    class Solution {
    public:
        vector<string> removeInvalidParentheses(const string& s) {
            unordered_set<string> table;
            int len = 0;
            helper(len, table, s, "", 0, 0);
    
            vector<string> result;
            for (auto p : table) result.push_back(p);
            return result;
        }
    
        void helper(int& len, unordered_set<string>& r, const string& s, string buf, int index, int stack) {
            if (index == s.size()) {
                if (stack == 0) {
                    if (buf.size() > len) {
                        len = buf.size();
                        r.clear();
                        r.insert(buf);
    
                    } else if (buf.size() == len) {
                        r.insert(buf);
                    }
                }
                return;
            }
            if (stack < 0) return;
            if (s.size() - index + buf.size() < len) return;
            if (s[index] == '(') {
                helper(len, r, s, buf + "(", index + 1, stack + 1);
            } else if (s[index] == ')') {
                helper(len, r, s, buf + ")", index + 1, stack - 1);
            } else {
                buf.push_back(s[index]);
            }
            helper(len, r, s, buf, index + 1, stack);
        }
    };

  • 0

    The test cases don't have super long input strings :)


  • 0
    H

    I initially insert several large test cases like 40+ len, but now they got all removed. :(


Log in to reply
 

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