leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0301.cpp (1043B)

      1 class Solution {
      2     unordered_set<string> st;
      3     int maxi = 0;
      4 
      5     void rec(const string &s, int idx, const string &crnt, int open, int close) {
      6         if (idx == size(s)) {
      7             if (open != 0) return;
      8 
      9             if (size(crnt) > maxi) {
     10                 maxi = size(crnt);
     11                 st.clear();
     12             }
     13 
     14             if (size(crnt) == maxi && !st.count(crnt)) {
     15                 st.insert(crnt);
     16             }
     17 
     18             return;
     19         }
     20 
     21         if (s[idx] == '(') {
     22             if (open + 1 <= close) rec(s, idx + 1, crnt + '(', open + 1, close);
     23             rec(s, idx + 1, crnt, open, close);
     24         } else if (s[idx] == ')') {
     25             if (open > 0) rec(s, idx + 1, crnt + ')', open - 1, close - 1);
     26             rec(s, idx + 1, crnt, open, close);
     27         } else
     28             rec(s, idx + 1, crnt + s[idx], open, close);
     29     }
     30 
     31   public:
     32     vector<string> removeInvalidParentheses(const string &s) {
     33         rec(s, 0, "", 0, count(begin(s), end(s), ')'));
     34         return vector(begin(st), end(st));
     35     }
     36 };