Написано: 17.03.2023

301. Удаление неверных скобок (Remove Invalid Parentheses)

hard

Задание.

Дана строка s, содержащая круглые скобки и буквы.

Удалите минимальное количество недопустимых круглых скобок, чтобы сделать входную строку допустимой.

Верните список уникальных строк, которые допустимы при минимальном количестве удалений. Ответ можно вернуть в любом порядке.

Пример 1.

Входные данные: s = “()())()”

Результат: [”(())()”,”()()()”]

Пример 2.

Входные данные: s = “(a)())()”

Результат: [“(a())()”,”(a)()()”]

Пример 3.

Входные данные: s = “)(“

Результат: [””]

Решение 1 (рекурсивное).

class Solution {
private:
    vector<string> ans;
    unordered_set<string> uset; 
    int countRemoval(string s){
        stack<char> st;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                st.push('(');
            }
            else if(s[i]==')'){
                if(st.size()==0){
                    st.push(')');
                }
                else if(st.top()==')'){
                    st.push(')');
                }
                else if(st.top()=='('){
                    st.pop();
                }
            }
        }
        
        int invalid=st.size(); //minimum removals
        
        return invalid;
    }
   
    void helper(int invalid,string s){
        if(invalid<0) return;
        if(invalid==0){ 
            int invalidNow=countRemoval(s);
            if(invalidNow==0){
                ans.push_back(s);
            }
            return;
        }
      for(int i=0;i<s.size();i++){
          if (s[i] != ')' && s[i] != '(')
                {
                continue;
                }
          
          string left=s.substr(0,i);
          string right=s.substr(i+1);
          string temp=left+right;
          if(uset.find(temp)==uset.end()){
              uset.insert(temp);
            helper(invalid-1,temp);       
          }
               
      }  
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        int invalid=countRemoval(s);
        helper(invalid,s);
        return ans;
    }
};

Решение 2 (BFS).

class Solution {
private:
    bool check(string s)
    {
        int count = 0;
            for (const char ch : s) {
                if (ch == '(') count++;
                if (ch == ')') count--;
                if (count < 0) return false;
            }
            return count == 0;
    }
public:
    vector<string> removeInvalidParentheses(string s)
    {
        queue<string> q;
        q.push(s);
        vector<string> ret;
        unordered_set<string> v;
        int flag = 0;
        while(q.empty() == false && flag == 0) {
            int n=q.size();
            for(int i=0;i<n;++i)
            {
                string a=q.front();
                q.pop();
                if(check(a) == true) {
                    ret.push_back(a);
                    flag = 1;
                } else if(flag == 0) {
                    // решение ещё не найдено на данном уровне
                    for(int j=0;j<(int)a.length();++j) {
                        // проход по строке
                        string t=a;
                        if(a[j]=='('||a[j]==')') {
                            // удаляем каждую встреченную скобку
                            t.erase(j,1);
                            if(v.find(t) == v.end()) {
                                // добавляем строчку в очередь, если такая прежде не встречалась
                                q.push(t);
                                v.insert(t);
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};