python, bfs/dfs/union find, complexity analysis
BFS w/o memo: beats 5.81%\n\n\nclass Solution:\n    def smallestEquivalentString(self, A, B, S):\n\t\t\'\'\'step1: Create a mapping from each char to its direct
**BFS w/o memo: beats 5.81%**\n\n```\nclass Solution:\n    def smallestEquivalentString(self, A, B, S):\n\t\t\'\'\'step1: Create a mapping from each char to its direct equivalents.\'\'\'\n        neighbors = collections.defaultdict(set)\n        for a, b in zip(A, B):\n            neighbors[a].add(b)\n            neighbors[b].add(a)\n\t\t\n\t\t\'\'\'step2: For each char of S, explore the map of all equivalents (marke as seen) \n\t\tand memoize the minimum equivalents.\'\'\'\n        d = {i:i for i in S}\n\n        def bfs(ch):\n            res = ch\n            seen = set()\n            queue = {ch}\n\n            while queue:\n                c = queue.pop()\n                if c in seen: continue\n                seen.add(c)\n                res = min(res, c)\n                queue |= neighbors[c]\n\n            for v in seen:\n                d[v] = res\n\n            return res\n        return \'\'.join(bfs(c) for c  in S)\n```\n\n**BFS w/ memo: beats 99.35%**\n\n```\nclass Solution:\n    def smallestEquivalentString(self, A, B, S):\n        neighbors = collections.defaultdict(set)\n        for a, b in zip(A, B):\n            neighbors[a].add(b)\n            neighbors[b].add(a)\n\n        memo = {}\n\n        def bfs(ch):\n            if ch in memo: return memo[ch]\n            res = ch\n            seen = set()\n            queue = {ch}\n\n            while queue:\n                c = queue.pop()\n                if c in seen: continue\n                seen.add(c)\n                res = min(res, c)\n                queue |= neighbors[c]\n\n            for v in seen:\n                memo[v] = res\n\n            return res\n        return \'\'.join(bfs(c) for c  in S)\n        \n```\n\n**DFS: beats 5.8%**\n\n```\nclass Solution(object):   \n    def smallestEquivalentString(self, A, B, S):\n        neighbors = collections.defaultdict(set)\n        for a, b in zip(A, B):\n            neighbors[a].add(b)\n            neighbors[b].add(a)\n        \n        visited = set()\n        def dfs(ch, minChar, visited):\n            visited.add(ch)\n            res = minChar\n            \n            for nei in neighbors[ch]:\n                if nei not in visited:\n                    res = min(res, dfs(nei, min(minChar, nei), visited))\n            return res\n\n\n        return \'\'.join([dfs(c, c, set()) for c in S])\n```\n\n\n\n**Union Find: beats 97.42%**\n\n```\nclass Solution:\n    def smallestEquivalentString(self, A: str, B: str, S: str) -> str:\n\t    \'\'\'\n        step1: model these equalities as edges in a graph\n        step2: compute connected components of the graph ==> {node: commID}\n        step3: convert \'s\'\n        \'\'\'\n        # step 1 & 2\n        d = {i:i for i in string.ascii_lowercase}\n        \n        def find(x):\n            if d[x] != x:\n                d[x] = find(d[x])\n            return d[x]\n        \n        def union(x, y):\n            rx, ry = find(x), find(y)\n            if d[rx] < d[ry]:\n                d[ry] = rx\n            else:\n                d[rx] = ry\n        \n        for a, b in zip(A, B):\n            union(a, b)\n\t\t\t\n        # step3\n        ans = \'\'\n        for s in S:\n            ans += find(s)\n        return ans\n```\n\n**Complexity:**\n* Time: O(max(n, m)) where n is length of A, and m is length of S.\n* space: O(1).  Since we only need to store the 26 English characters.
[]