Determine if two sentences are similar.
Medium
Determine if Two Sentences Are Similar. Two sentences are similar if they have the same length and each pair of corresponding words in the two sentences is similar. The similarity between words is defined by the provided list of similar word pairs. A word is always similar to itself.
For example, if we have the list of similar word pairs as [("great", "good"), ("acting","drama"), ("skills","talent")], then the sentences "You have great acting skills" and "You have good drama talent" are similar.
Examples
sentence1 = ["Let's", "code", "in", "Python"] sentence2 = ["Let's", "program", "in", "Python"] similarPairs = [ ("code", "program"), ] output: true sentence1 = ["I", "love", "to", "play", "football"] sentence2 = ["I", "love", "playing", "soccer"] similarPairs = [("play", "playing"), ("football", "soccer")] output: false, different sentence lengths sentence1 = ["Do", "you", "like", "coffee"] sentence2 = ["Do", "you", "love", "coffee"] similarPairs = [ ("like", "enjoy"), ("coffee", "tea"), ] output: false # "like" is not similar to "love" based on the given pairs. sentence1 = ["I", "really", "love", "leetcode", "and", "apples"] sentence2 = ["I", "so", "like", "codesignal", "and", "oranges"] similarPairs = [ ("very", "so"), ("love", "adore"), ("really", "very"), ("leetcode", "codesignal"), ("apples", "oranges"), ("like", "adore"), ] output: true
The provided solution checks if two given sentences are similar by using a graph-based approach. It constructs a graph where words are connected if they are similar according to the provided pairs. Then, it performs a depth-first search (DFS) to check if each pair of corresponding words from the two sentences are connected in the graph.
The Depth-First Search (DFS) algorithm is well-suited for this question as it efficiently explores the graph structure created from the similar word pairs. DFS is ideal for checking connectivity between words, which aligns with the task of determining if two words are similar based on the provided pairs. Its memory efficiency is beneficial for handling potentially large sets of sentences and word pairs. Additionally, DFS offers a simple implementation, either through recursion or using a stack, which aids in writing clean and understandable code. Its flexibility allows for easy modification to incorporate additional constraints or optimizations if needed. Therefore, DFS provides an elegant and effective solution for traversing the graph and determining sentence similarity.
Remember to handle potential off-by-one errors when implementing this solution due to index-based iteration over the sentences.
Time Complexity: Let n be the maximum number of words in the sentences, and m be the number of similar word pairs. Constructing the graph takes O(m) time. Then, for each word pair, the DFS takes O(n) time in the worst case, resulting in a total time complexity of O(n + m).
Space Complexity: In the worst case, the graph can contain O(m) edges. Additionally, in the DFS, the space complexity is O(n) due to the recursion stack or auxiliary data structures to track visited nodes. Therefore, the overall space complexity is O(n + m).
Watch Simon, software engineer at Google, answer the question "determine if two sentences are similar."
Related questions
Determine if a number is a power of two.Determine if two words are sorted in lexicographic order.Related courses
