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]
andsentence2[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.
OR
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:
|
|
Example 2:
|
|
Example 3:
|
|
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).
- We will use a
- 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
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n + k)
, wheren
is the length of the sentences andk
is the number of similar pairs. We traverse the sentences once (O(n)
) and construct the similarity set inO(k)
time. - 🧺 Space complexity:
O(k)
, the space complexity is primarily due to storing the similarity pairs in the set, which requiresO(k)
space.