[Python] Union Find - Daily Challenge Jan., Day 14
Intuition\n Describe your first thoughts on how to solve this problem. \nfirst, I examine these three property \n- reflexivity\neach character equals itself\na:
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nfirst, I examine these three property \n- **reflexivity**\neach character equals itself\na: [a]\nb: [b]\n\n- **symmetry**\nif a == b, then they can equals each other.\nsince we need lexicographically smallest one, both `a` and `b` belongs to `[a,b]` group\na: [a, b]\nb: [b, a] = [a, b]\n\n- **transitivity**\na: [a, b, c]\nb: [b, a]\nif a == c, then b == a == c. this means once `a == b`, no matter one of them equals any other character, they are all in the same group\n\n    a: [a,b,c]\n    b: [b,a] = [b, [a,b,c]] = b union a = [a,b,c]\n\nit seems like a disjoint set problem, thus, we can use union-find to help us union them into each group.\n\nand we **Always** union lexicographically larger one to lexicographically smaller one\n\nonce we have all these groups, we just find character by character in `baseStr` from our union-find, and it\'ll always find the lexicographically smallest character back to us.\n\n# Approach\n\n1. union `s1` and `s2` character by character\n2. find character by character in `baseStr` in our union-find\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(26)$$\n\n# Code\n```\nclass Solution:\n    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n        parent = [i for i in range(26)] # each english letter\'s parent\n\n        def find(x):\n            if parent[x] != x:\n                parent[x] = find(parent[x])\n            return parent[x]\n\n        def union(a, b):\n            pa, pb = find(a), find(b)\n            if pa == pb: return\n            if pa < pb: # union to Lexicographically smaller one\n                parent[pb] = pa\n            else:\n                parent[pa] = pb\n        \n        for a, b in zip(s1, s2):\n            union(ord(a)-ord("a"), ord(b)-ord("a"))\n\n        res = ""\n        for ch in baseStr:\n            res += chr(ord("a")+find(ord(ch)-ord("a")))\n        return res\n```
['Union Find', 'Python3']