Задача: 301. Remove Invalid Parentheses
Сложность: hard

Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой.

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

Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

👨‍💻 Алгоритм:

1⃣Инициализация:
Инициализируйте массив, который будет хранить все допустимые выражения.
Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо.
Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно.

2⃣Обработка текущего символа:
Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии.
Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения.

3⃣Завершение рекурсии и проверка:
Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны).
Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор.
Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений.

😎 Решение:

class Solution:
    def __init__(self):
        self.valid_expressions = set()
        self.minimum_removed = float('inf')

    def reset(self):
        self.valid_expressions.clear()
        self.minimum_removed = float('inf')

    def recurse(self, s, index, left_count, right_count, expression, removed_count):
        if index == len(s):
            if left_count == right_count:
                if removed_count <= self.minimum_removed:
                    possible_answer = "".join(expression)
                    if removed_count < self.minimum_removed:
                        self.valid_expressions.clear()
                        self.minimum_removed = removed_count
                    self.valid_expressions.add(possible_answer)
            return

        current_character = s[index]
        length = len(expression)

        if current_character != '(' and current_character != ')':
            expression.append(current_character)
            self.recurse(s, index + 1, left_count, right_count, expression, removed_count)
            expression.pop()
        else:
            self.recurse(s, index + 1, left_count, right_count, expression, removed_count + 1)
            expression.append(current_character)

            if current_character == '(':
                self.recurse(s, index + 1, left_count + 1, right_count, expression, removed_count)
            elif right_count < left_count:
                self.recurse(s, index + 1, left_count, right_count + 1, expression, removed_count)

            expression.pop()

    def removeInvalidParentheses(self, s: str) -> [str]:
        self.reset()
        self.recurse(s, 0, 0, 0, [], 0)
        return list(self.valid_expressions)

Ставь 👍 и забирай 📚 Базу знаний