Сложность: 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:
def checkValidString(self, s: str) -> bool:
memo = [[-1] * len(s) for _ in range(len(s))]
return self.isValidString(0, 0, s, memo)
def isValidString(self, index: int, openCount: int, s: str, memo: list) -> bool:
if index == len(s):
return openCount == 0
if memo[index][openCount] != -1:
return memo[index][openCount] == 1
isValid = False
if s[index] == '*':
isValid = self.isValidString(index + 1, openCount + 1, s, memo)
if openCount > 0:
isValid = isValid or self.isValidString(index + 1, openCount - 1, s, memo)
isValid = isValid or self.isValidString(index + 1, openCount, s, memo)
elif s[index] == '(':
isValid = self.isValidString(index + 1, openCount + 1, s, memo)
elif openCount > 0:
isValid = self.isValidString(index + 1, openCount - 1, s, memo)
memo[index][openCount] = 1 if isValid else 0
return isValid
Ставь 👍 и забирай 📚 Базу знаний