Проверка соответствия последовательности строк заданному шаблону

Условие

Даны два входных параметра: строка pattern, содержащая только строчные латинские буквы, и массив строк s. Требуется реализовать функцию matchPattern, которая проверяет, можно ли установить взаимно‑однозначное соответствие между символами pattern и элементами массива s. Иными словами, каждому символу pattern должна соответствовать ровно одна строка из s, и каждой строке из s должен соответствовать единственный символ pattern. Функция должна вернуть true, если такое биективное сопоставление возможно, иначе – false.

/*
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
*/

bool matchPattern(const std::vector<std::string>& str, const std::string& pattern)
{
    
}

Ответ

Храните соответствия в обе стороны: символ → слово и слово → символ. Одной таблицы недостаточно, иначе разным символам можно ошибочно сопоставить одно слово.

bool matchPattern(const std::vector<std::string>& words,
                  const std::string& pattern) {
    if (words.size() != pattern.size()) return false;
    std::unordered_map<char, std::string> forward;
    std::unordered_map<std::string, char> backward;
    for (std::size_t i = 0; i < words.size(); ++i) {
        const char letter = pattern[i];
        const auto& word = words[i];
        auto a = forward.find(letter);
        auto b = backward.find(word);
        if (a != forward.end() && a->second != word) return false;
        if (b != backward.end() && b->second != letter) return false;
        forward.emplace(letter, word);
        backward.emplace(word, letter);
    }
    return true;
}

Нужны , и <unordered_map>. При обычном поведении хеш-таблиц время линейно по суммарной длине входа, поскольку строки тоже нужно хешировать и сравнивать. Два пустых входа считаются соответствующими.