Python3 Simple Depth-First Search
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is obviously an undirected graph question at first glance, so we will connect the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is obviously an undirected graph question at first glance, so we will connect the characters first. Also, to avoid repeating search when constructing smallest ```baseStr```, we will find the smallest character for each character first and store them inside a dictionary ```smallest```. We will use DFS to traverse the adjacent characters.\n\nHow do we do that? We can iterate from \'a\' to \'z\' using an iterator, lets say ```i``` and if ```i``` is in the graph, then set the smallest character for all the adjacent characters to ```i```. This works because we iterate the characters in ascending order. Thus, the adjacent nodes will be set to the smallest character in the relationship\n\n# Code\n```\nclass Solution:\n    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n        equiv = defaultdict(set)\n        smallest = defaultdict(str)\n\n        for c1, c2 in zip(s1, s2):\n            if c1 == c2: continue\n            equiv[c1].add(c2)\n            equiv[c2].add(c1)\n        \n        def setMinChar(curr, minCh):\n            if curr in smallest: return\n            smallest[curr] = minCh\n            for eq in equiv[curr]:\n                setMinChar(eq, minCh)\n\n        for c in [chr(ord(\'a\') + i) for i in range(26)]:\n            if c in equiv:\n                if c in smallest: continue\n                setMinChar(c, c)\n        return \'\'.join([smallest[c] if c in smallest else c for c in baseStr])\n```
['Depth-First Search', 'Python3']