Problem statement

https://leetcode.com/problems/sentence-similarity-ii/

Solution

Natural extension of problem 0734, here we need to create graph of connections. Then we just can perform dfs for each pair in pairs and have O(P * N) time complexity, where P is size of pairs and N is size of words1 and words2. We can also perform dfs only once and find connected components in graph in O(N) time and then for each pair check similarity in O(1).

Complexity

Overall complexity is O(N+P). Space complexity is O(N).

Code

class Solution:
    def areSentencesSimilarTwo(self, words1, words2, pairs):
        G, V, comps, idx = defaultdict(list), set(), {}, 0
        for x, y in pairs:
            G[x].append(y)
            G[y].append(x)

        def dfs(node, idx):
            V.add(node)
            comps[node] = idx
            for child in G[node]:
                if child not in V:
                    dfs(child, idx)

        for node in G.keys():
            if node not in V:
                dfs(node, idx)
                idx += 1
                
        if len(words1) != len(words2): return False

        for x, y in zip(words1, words2):
            if x != y and comps.get(x, -1) != comps.get(y, -2): return False

        return True

Remark

Finally, there is Union Find approach, where we again found connected components with the same complexity.