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

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если 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 {
    func checkValidString(_ s: String) -> Bool {
        var memo = Array(repeating: Array(repeating: -1, count: s.count), count: s.count)
        return isValidString(0, 0, s, &memo)
    }
    
    private func isValidString(_ index: Int, _ openCount: Int, _ str: String, _ memo: inout [[Int]]) -> Bool {
        if index == str.count {
            return openCount == 0
        }
        
        if memo[index][openCount] != -1 {
            return memo[index][openCount] == 1
        }
        
        var isValid = false
        let currentIndex = str.index(str.startIndex, offsetBy: index)
        
        if str[currentIndex] == "*" {
            isValid = isValidString(index + 1, openCount + 1, str, &memo)
            if openCount > 0 {
                isValid = isValid || isValidString(index + 1, openCount - 1, str, &memo)
            }
            isValid = isValid || isValidString(index + 1, openCount, str, &memo)
        } else if str[currentIndex] == "(" {
            isValid = isValidString(index + 1, openCount + 1, str, &memo)
        } else if openCount > 0 {
            isValid = isValidString(index + 1, openCount - 1, str, &memo)
        }
        
        memo[index][openCount] = isValid ? 1 : 0
        return isValid
    }
}

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