O(|answer|), no superfluous enumeration


  • 0
    M
    /// O(|ans|). no superfluous enumeration
    
    #define REP(i, n) for (int i = 0; i < (n); i++)
    #define ROF(i, a, b) for (int i = (b); --i >= (a); )
    
    class Solution {
      vector<string> halves, res;
      vector<int> milestones, milestones2;
      int split;
      // enumerate valid left part: s[0 , split)
      // invariant: for close parentheses in s[0 , milestones[i]], at least `i+1` of them must be removed
      void forward(const string &s, string ss, int k, int i, int removed, bool can) {
        if (k == split) {
          halves.push_back(ss);
          return;
        }
        if (s[k] == ')') {
          int ii = k == milestones[i] ? i+1 : i;
          if (can && removed < milestones.size()) // prefixes of continuous close parentheses can be removed, other parts are disallowed
            forward(s, ss, k+1, ii, removed+1, true);
          if (k < milestones[i] || removed > i) // if k == milestones[i], comply with the invariant
            forward(s, ss+s[k], k+1, ii, removed, false);
        } else
          forward(s, ss+s[k], k+1, i, removed, true);
      }
      // enumerate valid right part: s[split, n)
      // for open parentheses in s[milestones2[i] , n), at least `i+1` of them must be removed
      void backward(const string &s, string ss, int k, int i, int removed, bool can) {
        if (k == split) {
          reverse(ss.begin(), ss.end());
          for (auto &x: halves)
            res.push_back(x+ss);
          return;
        }
        k--;
        if (s[k] == '(') {
          int ii = i < milestones2.size() && k == milestones2[i] ? i+1 : i;
          if (can && removed < milestones2.size()) // suffixes of continuous open parentheses can be removed, other parts are disallowed
            backward(s, ss, k, ii, removed+1, true);
          if (i == milestones2.size() || k > milestones2[i] || removed > i) // if k == milestones2[i], comply with the invariant
            backward(s, ss+s[k], k, ii, removed, false);
        } else
          backward(s, ss+s[k], k, i, removed, true);
      }
    public:
      vector<string> removeInvalidParentheses(string s) {
        int unmatched = 0;
        REP(i, s.size())
          if (s[i] == '(')
            unmatched++;
          else if (s[i] == ')') {
            if (unmatched > 0)
              unmatched--;
            else
              milestones.push_back(i);
          }
        split = milestones.empty() ? 0 : milestones.back()+1;
        unmatched = 0;
        ROF(i, split, s.size())
          if (s[i] == ')')
            unmatched++;
          else if (s[i] == '(') {
            if (unmatched > 0)
              unmatched--;
            else
              milestones2.push_back(i);
          }
        forward(s, "", 0, 0, 0, true);
        backward(s, "", s.size(), 0, 0, true);
        return res;
      }
    };
    

    https://github.com/MaskRay/LeetCode/blob/master/remove-invalid-parentheses.cc


Log in to reply
 

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