刪除無效圓括號 - Leetcode時間複雜度

Question

我在leetcode上解決了這個問題，問題陳述如下。

刪除無效括號的最小數目以使輸入字符串有效。返回所有可能的結果。

注意：輸入字符串可能包含除括號（和）以外的其他字母。

Examples: 
"()())()" -> ["()()()", "(())()"] 
"(a)())()" -> ["(a)()()", "(a())()"] 
")(" -> [""] 

我在一段時間後能夠解決問題。但是我無法找到解決方案的時間複雜性。我的代碼如下。請幫助我找到時間複雜性。

class Solution { 
public: 

    void balance(string s, int curr_index, int changes, int max_changes, unordered_set<string> &memo, vector<string> &result){ 

     if(memo.find(s) != memo.end()){ 
      return; 
     } 

     if(changes == max_changes){ 
      int opening = 0; 
      for(int i = 0; i < s.length(); i++){ 
       if(s[i] == '('){ 
        opening++; 
       } 
       else if(s[i] == ')'){ 
        if(opening == 0){ 
         return; 
        } 
        else{ 
         opening--; 
        } 
       } 
      } 
      if(opening == 0){ 
       result.push_back(s); 
      } 
     } 
     else if(changes > max_changes || curr_index >= s.length()){ 
      return; 
     } 
     else{ 
      if(s[curr_index] == '(' || s[curr_index] == ')'){ 
       string temp = s; 
       temp.erase(temp.begin() + curr_index); 
       balance(temp, curr_index, changes + 1, max_changes, memo, result); 
      } 

      balance(s, curr_index + 1, changes, max_changes, memo, result); 
     } 

     memo.insert(s); 

    } 


    vector<string> removeInvalidParentheses(string s) { 

     int opening = 0; 
     int min_changes = 0; 

     vector<string> result; 

     for(int i = 0; i < s.length(); i++){ 
      if(s[i] == ')' && opening == 0){ 
       min_changes++; 
      } 
      else if(s[i] == ')' && opening != 0){ 
       opening--; 
      } 
      else if(s[i] == '('){ 
       opening++; 
      } 
     } 

     min_changes += opening; 

     if(min_changes == s.length()){ 
      result.push_back(""); 
      return result; 
     } 
     else{ 

      unordered_set<string> memo; 

      balance(s, 0, 0, min_changes, memo, result); 

      return result; 
     } 

    } 
    }; 

Answer 1

它是指數型的。沒有什麼可以做的，因爲輸出大小可能是指數級的。

考慮以下示例：(a(a(a(a.....))))))，其中對(a的數量是右括號的兩倍。很明顯，我們需要刪除開頭括號的一半，並且很明顯，刪除它們的任何子集都會生成唯一的字符串。

設字符串的長度爲5n。然後我們有2n'（'和'a'和n'）''。有2n選擇n方法來刪除左括號的子集並獲得一個有效的字符串，這是一個字符串長度的指數。