Sentence Similarity

To determine if two sentences are similar, they must have the same length and each word in the same position in both sentences must be either identical or similar. Similarity between words is defined by the similarPairs list.

In the Python solution below, we’ll first check if the sentences have the same length. If not, we can return False immediately. Then we’ll convert similarPairs into a set for quick lookup. Then we’ll iterate over each word in the sentences. If a word from sentence1 and sentence2 is not the same and also not in the similarPairs set, we return False. If we finish the iteration without returning False, it means all words are similar, so we return True.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:
        # Check if sentences have the same length
        if len(sentence1) != len(sentence2):
            return False

        # Convert similarPairs into a set
        similarPairsSet = set(map(tuple, similarPairs))

        # Iterate over each word in the sentences
        for w1, w2 in zip(sentence1, sentence2):
            # If words are not the same and not similar, return False
            if w1 != w2 and (w1, w2) not in similarPairsSet and (w2, w1) not in similarPairsSet:
                return False

        # All words are similar
        return True

This solution has a time complexity of O(n), where n is the maximum length of the sentences, because we iterate over each word in the sentences. The space complexity is O(m), where m is the number of similarPairs, because we convert similarPairs into a set.