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

😎 Решение:

func areSentencesSimilar(_ sentence1: [String], _ sentence2: [String], _ similarPairs: [[String]]) -> Bool {
    if sentence1.count != sentence2.count {
        return false
    }
    
    var graph = [String: [String]]()
    for pair in similarPairs {
        let (x, y) = (pair[0], pair[1])
        graph[x, default: []].append(y)
        graph[y, default: []].append(x)
    }
    
    func dfs(_ word1: String, _ word2: String, _ visited: inout Set<String>) -> Bool {
        if word1 == word2 {
            return true
        }
        visited.insert(word1)
        for neighbor in graph[word1, default: []] {
            if !visited.contains(neighbor) && dfs(neighbor, word2, &visited) {
                return true
            }
        }
        return false
    }
    
    for (w1, w2) in zip(sentence1, sentence2) {
        if w1 != w2 {
            var visited = Set<String>()
            if !dfs(w1, w2, &visited) {
                return false
            }
        }
    }
    
    return true
}

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