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

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Биекция между символами шаблона и подстроками строки: каждый символ → уникальная подстрока и наоборот.

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true

👨‍💻 Алгоритм

1⃣Создайте отображения:
symbolMap: символ шаблона → строка
wordSet: множество уже использованных строк
Запустите рекурсивную функцию isMatch с текущими индексами строки и шаблона.

2⃣Базовые случаи:
Если дошли до конца шаблона и строки одновременно — верните true.
Если один из них завершился, а другой — нет, верните false.
Если символ шаблона уже связан со строкой:
Проверьте, начинается ли s с этой подстроки — если нет, верните false
Иначе продолжайте рекурсию с обновлённым индексом

3⃣Если символ ещё не связан:
Переберите возможные подстроки из s, начиная с текущего индекса
Пропустите уже использованные строки (из wordSet)
Свяжите символ с подстрокой, запустите рекурсию
Если вернулась true — победа
Иначе — backtrack (удалите из отображения и множества)

😎 Решение

#include <unordered_map>
#include <unordered_set>
#include <string>

class Solution {
public:
    bool wordPatternMatch(std::string pattern, std::string s) {
        std::unordered_map<char, std::string> symbolMap;
        std::unordered_set<std::string> wordSet;
        return isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

private:
    bool isMatch(const std::string& s, int sIndex, const std::string& pattern, int pIndex,
                 std::unordered_map<char, std::string>& symbolMap, std::unordered_set<std::string>& wordSet) {
        if (pIndex == pattern.size()) return sIndex == s.size();

        char symbol = pattern[pIndex];

        if (symbolMap.count(symbol)) {
            const std::string& word = symbolMap[symbol];
            if (s.substr(sIndex, word.size()) != word) return false;
            return isMatch(s, sIndex + word.size(), pattern, pIndex + 1, symbolMap, wordSet);
        }

        for (int end = sIndex + 1; end <= s.size(); ++end) {
            std::string candidate = s.substr(sIndex, end - sIndex);
            if (wordSet.count(candidate)) continue;

            symbolMap[symbol] = candidate;
            wordSet.insert(candidate);

            if (isMatch(s, end, pattern, pIndex + 1, symbolMap, wordSet)) return true;

            symbolMap.erase(symbol);
            wordSet.erase(candidate);
        }

        return false;
    }
};

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