Practice/Google/Leetcode 737. Sentence Similarity II

Leetcode 737. Sentence Similarity II

CodingMust

Problem

You are given two arrays of words, words1 and words2, both of the same length. You are also given a list of word pairs where each pair [a, b] indicates that word a and word b are considered similar to each other.

The similarity relationship is transitive: if word a is similar to word b, and word b is similar to word c, then word a is also similar to word c. Additionally, every word is similar to itself.

Determine whether the two arrays represent equivalent sequences. Two arrays are equivalent if for every index i, the word at words1[i] is either identical to or similar to the word at words2[i].

Return true if the arrays are equivalent, and false otherwise.

Requirements

1. Compare words at corresponding positions in both arrays
2. Two words are equivalent if they are identical or connected through a chain of similarity pairs
3. Handle transitive relationships between words (if A ~ B and B ~ C, then A ~ C)
4. Return true only if all corresponding positions contain equivalent words

Constraints

• 1 ≤ words1.length, words2.length ≤ 1000
• words1.length == words2.length
• 1 ≤ words1[i].length, words2[i].length ≤ 20
• 0 ≤ pairs.length ≤ 2000
• pairs[i].length == 2
• 1 ≤ pairs[i][0].length, pairs[i][1].length ≤ 20
• All words consist of lowercase English letters
• Expected time complexity: O(n + p) where n is the number of words and p is the number of pairs
• Expected space complexity: O(p) for storing the similarity relationships

Examples

Example 1:

` Input: words1 = ["wonderful", "day"] words2 = ["great", "day"] pairs = [["wonderful", "great"]]

Output: true

Explanation:

• Position 0: "wonderful" is similar to "great" (direct pair)
• Position 1: "day" is identical to "day"
• All positions match, so return true `

Example 2:

` Input: words1 = ["fast", "car"] words2 = ["quick", "vehicle"] pairs = [["fast", "rapid"], ["rapid", "quick"], ["car", "auto"]]

Output: false

Explanation:

• Position 0: "fast" connects to "quick" through "rapid" (fast -> rapid -> quick)
• Position 1: "car" is similar to "auto", but not to "vehicle"
• Since position 1 doesn't match, return false `

Example 3:

` Input: words1 = ["one"] words2 = ["one"] pairs = []

Output: true

Explanation: The words are identical at the only position `