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 a list of similar word pairs pairs, determine if two sentences are similar.
You need to consider the following:
pairs list."great" and "good" are similar, and "fine" and "good" are similar, then "great" and "fine" are considered similar.
Similarity is also symmetric. For example, "great" is similar to "fine" implies that "fine" is similar to "great".
Return true if sentence1 and sentence2 are similar, otherwise return false.
Example 1:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], pairs = [["great","fine"],["acting","drama"],["skills","talent"]] Output: true Explanation: The two sentences have equal lengths and each word i of sentence1 is also similar to the corresponding word in sentence2.
Example 2:
Input: sentence1 = ["great"], sentence2 = ["great"], pairs = [] Output: true Explanation: The two sentences are identical.
Example 3:
Input: sentence1 = ["great"], sentence2 = ["fine"], pairs = [] Output: false Explanation: The two sentences have different words and are not similar.
Example 4:
Input: sentence1 = ["great"], sentence2 = ["fine"], pairs = [["great","fine"]] Output: true Explanation: The two sentences have different words but are similar.
Example 5:
Input: sentence1 = ["eating","pizza"], sentence2 = ["eat","pizza"], pairs = [["eating","eat"],["lasagna","pasta"]] Output: false
Constraints:
1 <= sentence1.length, sentence2.length <= 10001 <= sentence1[i].length, sentence2[x].length <= 20sentence1[i] and sentence2[x] consist of lower-case English letters.0 <= pairs.length <= 20000 <= pairs[i].length == 21 <= pairs[i][0].length, pairs[i][1].length <= 20pairs[i][0] and pairs[i][1] consist of lower-case English letters.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
To determine if two sentences are similar using a brute-force approach, we directly compare words between sentences. This involves examining every possible pair of words or phrases to check for a match based on some criteria of similarity.
Here's how the algorithm would work step-by-step:
def are_sentences_similar_brute_force(sentence1, sentence2, similar_pairs, threshold):
words_in_sentence1 = sentence1.lower().split()
words_in_sentence2 = sentence2.lower().split()
number_of_words_in_sentence1 = len(words_in_sentence1)
number_of_words_in_sentence2 = len(words_in_sentence2)
if number_of_words_in_sentence1 == 0 or number_of_words_in_sentence2 == 0:
return False
matching_word_count = 0
# Iterate through all possible word pairs between sentences
for word_from_sentence1 in words_in_sentence1:
for word_from_sentence2 in words_in_sentence2:
# Check for exact word match
if word_from_sentence1 == word_from_sentence2:
matching_word_count += 1
continue
# Check if the words are in the list of similar pairs
if (word_from_sentence1, word_from_sentence2) in similar_pairs or \
(word_from_sentence2, word_from_sentence1) in similar_pairs:
matching_word_count += 1
# Calculate the percentage of matching words.
similarity_percentage = (matching_word_count / max(number_of_words_in_sentence1, number_of_words_in_sentence2)) * 100
# Return True if similarity is above the threshold
return similarity_percentage > thresholdTo efficiently determine sentence similarity, we leverage a set data structure for quick lookups. We pre-process the word pairs into sets to enable constant-time checks for similarity, allowing for fast comparison of sentences.
Here's how the algorithm would work step-by-step:
def are_sentences_similar(sentence1, sentence2, similar_pairs):
# Create a set of similar word pairs for fast lookup
similar_word_pair_sets = set()
for pair in similar_pairs:
similar_word_pair_sets.add(tuple(pair))
words1 = sentence1.split()
words2 = sentence2.split()
if len(words1) != len(words2):
return False
# Iterate through the words and compare them
for i in range(len(words1)):
word1 = words1[i]
word2 = words2[i]
# Check if the words are identical or in similar pairs
if word1 == word2:
continue
# Check if the reverse of the pair also exists
if (word1, word2) in similar_word_pair_sets or (word2, word1) in similar_word_pair_sets:
continue
# If none of the conditions are met, words are not similar
return False
# If all words are similar, return True
return True| Case | How to Handle |
|---|---|
| One or both input sentence arrays are null or empty | Return True if both are empty, False if only one is, based on problem definition. |
| Input sentences have significantly different lengths | If sentence lengths differ, return False immediately as they cannot be similar if not of equal length. |
| The word pairs array is null or empty | If the word pairs array is empty, sentence similarity depends on exact string equality, so check that. |
| The word pairs array contains null or empty strings | Handle null or empty strings by skipping the pair and continuing, or consider it as non-similar if appropriate for the problem. |
| The word pairs array contains duplicate word pairs | The union find or graph approach handles this naturally as the root will still be the same for the connected components. |
| Sentences contain words with different casing ('The' vs 'the') | Convert all words to lowercase before comparison to ensure case-insensitive matching. |
| Sentences contain punctuation or special characters | Remove punctuation and special characters from words before comparison, or handle them explicitly as part of the comparison. |
| Maximum length sentences exceeding memory constraints for large input sizes | Consider using a more memory-efficient data structure or algorithm, or reject overly long inputs gracefully. |