Sentence Similarity II Python Solution

lcpy gen -n 737   # by problem number
lcpy gen -s sentence_similarity_ii   # by problem name

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["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.

Input: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","onepiece"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
Output: true
Explanation: "leetcode" -> "platform" -> "anime" -> "manga" -> "onepiece".

Input: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","hunterXhunter"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
Output: false
Explanation: "leetcode" is not similar to "onepiece".

class Solution:
    # Time: O((n + m) * alpha(n)) for n pairs and m words
    # Space: O(n)
    def are_sentences_similar_two(
        self, sentence1: list[str], sentence2: list[str], similar_pairs: list[list[str]]
    ) -> bool:
        if len(sentence1) != len(sentence2):
            return False
        parent: dict[str, str] = {}

        def find(x: str) -> str:
            parent.setdefault(x, x)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in similar_pairs:
            parent.setdefault(a, a)
            parent.setdefault(b, b)
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb

        return all(x == y or find(x) == find(y) for x, y in zip(sentence1, sentence2, strict=True))