Sentence Similarity

Problem

We can represent a sentence as an array of words, for example, the sentence "I am happy with leetcode" can be represented as arr = ["I","am",happy","with","leetcode"].

Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar.

Return true if sentence1 and sentence2 are similar, or false if they are not similar.

Two sentences are similar if:

They have the same length (i.e., the same number of words)
sentence1[i] and sentence2[i] are similar.

Notice that a word is always similar to itself, also notice that the similarity relation is not transitive. For example, if the words a and b are similar, and the words b and c are similar, a and c are not necessarily similar.

You are given a set of synonyms, such as (big, large) and (eat, consume). Using this set, determine if two sentences with the same number of words are equivalent.

For example, the following two sentences are equivalent:

“He wants to eat food.”
“He wants to consume food.”

Note that the synonyms (a, b) and (a, c) do not necessarily imply (b, c): consider the case of (coach, bus) and (coach, teacher).

Examples

Example 1:

1
2
3
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true
Explanation: The two sentences have the same length and each word i of sentence1 is also similar to the corresponding word in sentence2.

Example 2:

1
2
3
Input: sentence1 = ["great"], sentence2 = ["great"], similarPairs = []
Output: true
Explanation: A word is similar to itself.

Example 3:

1
2
3
Input: sentence1 = ["great"], sentence2 = ["doubleplus","good"], similarPairs = [["great","doubleplus"]]
Output: false
Explanation: As they don't have the same length, we return false.

Follow up

What if we can assume that synonyms (a, b) and (a, c) do in fact imply (b, c)? For that refer Sentence Similarity 2 - with transitive word pairs.

Solution

Method 1 - Using Set

Here is the approach:

Check Lengths:
- First, we need to ensure that both sentences have the same length. If not, they cannot be similar.
Create a Similarity Map:
- We will use a set data structure to keep track of similar word pairs for quick lookup. Each pair will be stored in both directions (i.e., both (xi, yi) and (yi, xi) will be stored).
Check Each Word Pair:
- For each word position, check if the words from the two sentences are either the same or if they are marked as similar in our similarity map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) {
            return false;
        }

        Set<String> similaritySet = new HashSet<>();
        for (List<String> pair : similarPairs) {
            similaritySet.add(pair.get(0) + "#" + pair.get(1));
            similaritySet.add(pair.get(1) + "#" + pair.get(0));
        }

        for (int i = 0; i < sentence1.length; i++) {
            if (!sentence1[i].equals(sentence2[i]) && 
                !similaritySet.contains(sentence1[i] + "#" + sentence2[i])) {
                return false;
            }
        }

        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:
        if len(sentence1) != len(sentence2):
            return False
        
        similarity_set = set()
        for pair in similarPairs:
            similarity_set.add((pair[0], pair[1]))
            similarity_set.add((pair[1], pair[0]))
        
        for word1, word2 in zip(sentence1, sentence2):
            if word1 != word2 and (word1, word2) not in similarity_set:
                return False
        
        return True

Complexity

⏰ Time complexity: O(n + k), where n is the length of the sentences and k is the number of similar pairs. We traverse the sentences once (O(n)) and construct the similarity set in O(k) time.
🧺 Space complexity: O(k), the space complexity is primarily due to storing the similarity pairs in the set, which requires O(k) space.

Problem#

Examples#

Follow up#

Solution#

Method 1 - Using Set#

Code#

Complexity#