Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }

        unordered_map<string, vector<string>> graph;
        for (const auto& pair : similarPairs) {
            graph[pair[0]].push_back(pair[1]);
            graph[pair[1]].push_back(pair[0]);
        }

        for (size_t i = 0; i < sentence1.size(); ++i) {
            if (sentence1[i] != sentence2[i] && !dfs(sentence1[i], sentence2[i], graph, unordered_set<string>())) {
                return false;
            }
        }

        return true;
    }

private:
    bool dfs(const string& word1, const string& word2, unordered_map<string, vector<string>>& graph, unordered_set<string> visited) {
        if (word1 == word2) {
            return true;
        }
        visited.insert(word1);
        for (const string& neighbor : graph[word1]) {
            if (visited.find(neighbor) == visited.end() && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
};

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