Задача: 678. Valid Parenthesis String
Сложность: medium

Дана строка s, содержащая '(', ')' и '*'. Нужно определить, может ли она быть валидной скобочной последовательностью, если '*' может означать:
'('
')'
пустую строку ""

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

class Solution {
    function checkValidString($s) {
        $memo = array_fill(0, strlen($s), array_fill(0, strlen($s), -1));
        return $this->isValidString(0, 0, $s, $memo);
    }

    private function isValidString($index, $openCount, $str, &$memo) {
        if ($index == strlen($str)) {
            return $openCount == 0;
        }

        if ($memo[$index][$openCount] != -1) {
            return $memo[$index][$openCount] == 1;
        }

        $isValid = false;

        if ($str[$index] == '*') {
            $isValid = $this->isValidString($index + 1, $openCount + 1, $str, $memo);
            if ($openCount > 0) {
                $isValid = $isValid || $this->isValidString($index + 1, $openCount - 1, $str, $memo);
            }
            $isValid = $isValid || $this->isValidString($index + 1, $openCount, $str, $memo);
        } elseif ($str[$index] == '(') {
            $isValid = $this->isValidString($index + 1, $openCount + 1, $str, $memo);
        } elseif ($openCount > 0) {
            $isValid = $this->isValidString($index + 1, $openCount - 1, $str, $memo);
        }

        $memo[$index][$openCount] = $isValid ? 1 : 0;
        return $isValid;
    }
}

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