Sentence Similarity - Leetcode Solution

The Sentence Similarity problem on LeetCode is a problem that requires you to determine if two given sentences are similar or not.

For this problem, we are given two sentences as input: sentence1 and sentence2, both as lists of strings, and a list of pairs of strings called similarPairs. The objective is to determine if sentence1 and sentence2 are similar or not. To consider two sentences similar, they must have the same length and each pair of corresponding words must either be the same or must be in the similarPairs list.

The solution to this problem can be achieved through the use of a hash table or a dictionary. First, we will create a hash table or dictionary to store all the pairs of similar words. This will make it easier to check if a pair of corresponding words in the two given sentences are similar or not.

Then, we will check if the two sentences have the same length. If they do not have the same length, they cannot be similar. If they have the same length, we will then iterate through each pair of corresponding words in the two sentences and check if they are equal or if they are in the similarPairs hash table. If they are not equal and not in the hash table, we can safely say that the two sentences are not similar. If all the pairs of corresponding words in the two sentences are similar, we can say that the two sentences are similar.

Here is the detailed algorithm for solving the Sentence Similarity problem on LeetCode:

1. Create a hash table or dictionary to store all pairs of similar words in the similarPairs list.

   • Iterate over the pairs of words in the similarPairs list.
   • For each pair of words, add the pair to the hash table/dictionary (both the words can be used as keys).

2. Check if the lengths of sentence1 and sentence2 are equal.

   • If the lengths are not equal, return False because the two sentences cannot be similar.

3. Iterate through each pair of corresponding words in the two sentences, with the same index.

   • If the two words are equal, continue checking the next pair.
   • If the two words are not equal, check if they are in the hash table/dictionary. If they are, continue checking the next pair.
   • If the two words are not equal and not in the hash table/dictionary, return False because the two sentences are not similar.

4. If all the pairs of corresponding words in the two sentences are similar, return True because the two sentences are similar.

Here is the python code for the algorithm:

class Solution:
    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:
        
        # Create a hash table to store similar pairs of words
        similar_words = {}
        for w1, w2 in similarPairs:
            similar_words[w1] = w2
            similar_words[w2] = w1
        
        # Check if length of the sentences is the same
        if len(sentence1) != len(sentence2):
            return False
        
        # Check if each pair of corresponding words is similar
        for i in range(len(sentence1)):
            if sentence1[i] == sentence2[i]:
                continue
            elif sentence1[i] in similar_words and similar_words[sentence1[i]] == sentence2[i]:
                continue
            elif sentence2[i] in similar_words and similar_words[sentence2[i]] == sentence1[i]:
                continue
            else:
                return False
        
        # If all pairs of corresponding words are similar, return True
        return True

The time complexity of this algorithm is O(n), where n is the length of the sentences, because we are iterating through each word in both sentences. The space complexity of the algorithm is also O(n), because we are using a hash table to store the pairs of similar words.

1