Задача: 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 {
    private $validExpressions;
    private $minimumRemoved;

    function __construct() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function reset() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function recurse($s, $index, $leftCount, $rightCount, $expression, $removedCount) {
        if ($index === strlen($s)) {
            if ($leftCount === $rightCount) {
                if ($removedCount <= $this->minimumRemoved) {
                    $possibleAnswer = implode('', $expression);
                    if ($removedCount < $this->minimumRemoved) {
                        $this->validExpressions = [];
                        $this->minimumRemoved = $removedCount;
                    }
                    $this->validExpressions[$possibleAnswer] = true;
                }
            }
            return;
        }

        $currentCharacter = $s[$index];
        $length = count($expression);

        if ($currentCharacter !== '(' && $currentCharacter !== ')') {
            array_push($expression, $currentCharacter);
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount);
            array_pop($expression);
        } else {
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount + 1);
            array_push($expression, $currentCharacter);

            if ($currentCharacter === '(') {
                $this->recurse($s, $index + 1, $leftCount + 1, $rightCount, $expression, $removedCount);
            } else if ($rightCount < $leftCount) {
                $this->recurse($s, $index + 1, $leftCount, $rightCount + 1, $expression, $removedCount);
            }

            array_pop($expression);
        }
    }

    function removeInvalidParentheses($s) {
        $this->reset();
        $this->recurse($s, 0, 0, 0, [], 0);
        return array_keys($this->validExpressions);
    }
}

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