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

😎 Решение:
def areSentencesSimilar(sentence1, sentence2, similarPairs):
if len(sentence1) != len(sentence2):
return False

graph = {}
for x, y in similarPairs:
if x not in graph:
graph[x] = []
if y not in graph:
graph[y] = []
graph[x].append(y)
graph[y].append(x)

def dfs(word1, word2, visited):
if word1 == word2:
return True
visited.add(word1)
for neighbor in graph.get(word1, []):
if neighbor not in visited and dfs(neighbor, word2, visited):
return True
return False

for w1, w2 in zip(sentence1, sentence2):
if w1 != w2 and not dfs(w1, w2, set()):
return False

return True

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