Sentence Similarity Iii - Leetcode Solution

Problem Statement:

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, "great acting skills" and "fine drama talent" are similar if the similar word pairs are pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, then "great" and "good" are similar.

Also, similarity is symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.

And finally, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Example 1:

Input: words1 = ["great", "acting", "skills"], words2 = ["fine", "drama", "talent"], pairs = [["great", "fine"], ["drama","acting"], ["skills","talent"]]

Output: true

Explanation: "great" is similar to "fine", "acting" is similar to "drama", and "skills" is similar to "talent".

Example 2:

Input: words1 = ["an","extraordinary","meal"], words2 = ["one","good","dinner"], pairs = [["great", "fine"], ["drama","acting"], ["skills","talent"]]

Output: false

Explanation: The words do not have a valid one-to-one mapping between each other.

Solution:

We can approach this problem using graphs and depth-first search.

First, we need to build a graph where each node represents a word and its adjacent nodes represents its similar words.

Then, we perform depth-first search on this graph to check if the two sentences are similar.

To build the graph, we can use a dictionary where each word is a key and its value is a set of similar words.

For example, in the input: words1 = ["great", "acting", "skills"], words2 = ["fine", "drama", "talent"], pairs = [["great", "fine"], ["drama","acting"], ["skills","talent"]]

We can build the following graph: { "great": { "fine" }, "fine": { "great" }, "acting": { "drama" }, "drama": { "acting" }, "skills": { "talent" }, "talent": { "skills" } }

Then, we can perform depth-first search starting from each word in words1 and words2.

For each word, we check if its similar words have already been visited and if not, we mark them as visited and continue the search.

If the search from words1 and words2 intersect and have the same set of visited nodes, we return true, otherwise false.

Here's the Python code:

class Solution: def areSentencesSimilar(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool: if len(words1) != len(words2): return False

    # Build graph
    graph = {}
    for p in pairs:
        w1, w2 = p[0], p[1]
        graph.setdefault(w1, set()).add(w2)
        graph.setdefault(w2, set()).add(w1)
    
    # Depth-first search
    def dfs(word, visited):
        visited.add(word)
        for w in graph.get(word, set()):
            if w not in visited:
                dfs(w, visited)
    
    visited1, visited2 = set(), set()
    for i in range(len(words1)):
        if words1[i] == words2[i]:
            continue
        if words1[i] not in graph or words2[i] not in graph:
            return False
        if words1[i] not in visited1:
            dfs(words1[i], visited1)
        if words2[i] not in visited2:
            dfs(words2[i], visited2)
        if visited1 != visited2:
            return False
    
    return True

Time Complexity: O(n+p), where n is the length of the sentences and p is the number of pairs.

Space Complexity: O(p), where p is the number of pairs.

1