Problem statement

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

Solution

Just use defaultdict: for each word keep set of its similar words.

Complexity

Time complexity is O(N + M), where N is total length of all words in pairs and M is total length of all words in words1 + words2. Space complexity is O(N).

Code

class Solution:
    def areSentencesSimilar(self, words1, words2, pairs):
        d = defaultdict(set)
        for i, j in pairs:
            d[i].add(j)
            d[j].add(i)
            
        if len(words1) != len(words2): return False
        for w1, w2 in zip(words1, words2):
            if w1 != w2 and w1 not in d[w2]: return False
            
        return True