Задача: 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.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool CheckValidString(string s) {
        int n = s.Length;
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[n];
            Array.Fill(memo[i], -1);
        }
        return IsValidString(0, 0, s, memo);
    }

    private bool IsValidString(int index, int openCount, string str, int[][] memo) {
        if (index == str.Length) {
            return openCount == 0;
        }

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

        bool isValid = false;

        if (str[index] == '*') {
            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[index] == '(') {
            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;
    }
}

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