Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    wordPatternMatch(pattern, s) {
        const symbolMap = new Map();
        const wordSet = new Set();
        return this.isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

    isMatch(s, sIndex, pattern, pIndex, symbolMap, wordSet) {
        if (pIndex
        if (pIndex === pattern.length) {
            return sIndex === s.length;
        }
        const symbol = pattern[pIndex];
        if (symbolMap.has(symbol)) {
            const word = symbolMap.get(symbol);
            if (!s.startsWith(word, sIndex)) {
                return false;
            }
            return this.isMatch(s, sIndex + word.length, pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (let k = sIndex + 1; k <= s.length; k++) {
            const newWord = s.substring(sIndex, k);
            if (wordSet.has(newWord)) {
                continue;
            }
            symbolMap.set(symbol, newWord);
            wordSet.add(newWord);
            if (this.isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.delete(symbol);
            wordSet.delete(newWord);
        }
        return false;
    }
}

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