knakul853

Untitled

Nov 26th, 2020
686
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<string> removeInvalidParentheses(string s) {
  4.        
  5.         unordered_set<string>st;
  6.        
  7.         int lcnt = 0, rcnt = 0;
  8.        
  9.         for(char c:s){
  10.            
  11.             if(c == '(')lcnt++;
  12.             if(c == ')'){
  13.                
  14.                 if(lcnt > 0)
  15.                 {
  16.                     lcnt--;
  17.                 }
  18.                 else rcnt++;
  19.             }
  20.         }
  21.        
  22.         dfs(s, 0, lcnt, rcnt, 0, "", st);
  23.        
  24.         vector<string>ans(st.begin(), st.end());
  25.        
  26.         return ans;
  27.        
  28.     }
  29.    
  30.     void dfs(string s, int id, int lremove, int rremove, int pair, string path, unordered_set<string>&st )
  31.     {
  32.         if(id == s.size())
  33.         {
  34.             if( lremove == 0 && rremove == 0 && pair == 0)
  35.             {
  36.                 st.insert(path);
  37.             }
  38.             return;
  39.         }
  40.         if( lremove < 0 || rremove < 0 && pair < 0 ) return;
  41.         char c = s[id];
  42.        
  43.        if( c != '(' && c != ')')
  44.        {
  45.            dfs(s, id+1, lremove, rremove, pair, path+s[id], st);
  46.            return;
  47.        }
  48.        
  49.         if( c == ')')
  50.         {
  51.             if( rremove > 0 )
  52.             {
  53.                 dfs(s, id+1, lremove, rremove-1, pair, path, st);
  54.             }
  55.            
  56.             if( pair > 0 )
  57.                 dfs(s, id+1, lremove, rremove, pair-1, path+s[id], st);
  58.         }
  59.        
  60.           if( c == '(')
  61.         {
  62.             if( lremove > 0 )
  63.             {
  64.                 dfs(s, id+1, lremove-1, rremove, pair, path, st);
  65.             }
  66.             dfs(s, id+1, lremove, rremove, pair+1, path+s[id], st);
  67.         }
  68.          
  69.        
  70.     }
  71. };
RAW Paste Data