Задача: 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) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

var areSentencesSimilar = function(sentence1, sentence2, similarPairs) {
    if (sentence1.length !== sentence2.length) {
        return false;
    }

    const graph = {};
    for (const [x, y] of similarPairs) {
        if (!graph[x]) graph[x] = [];
        if (!graph[y]) graph[y] = [];
        graph[x].push(y);
        graph[y].push(x);
    }

    const dfs = (word1, word2, visited) => {
        if (word1 === word2) return true;
        visited.add(word1);
        for (const neighbor of graph[word1] || []) {
            if (!visited.has(neighbor) && dfs(neighbor, word2, visited)) {
                return true;
            }
        }
        return false;
    };

    for (let i = 0; i < sentence1.length; i++) {
        const w1 = sentence1[i], w2 = sentence2[i];
        if (w1 !== w2) {
            if (!dfs(w1, w2, new Set())) {
                return false;
            }
        }
    }

    return true;
};

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