LC: 1061. Lexicographically Smallest Equivalent String - spiralgo/algorithms GitHub Wiki

1061. Lexicographically Smallest Equivalent String:

The Essence:

The "equivalence" relationship between characters can be viewed as a graph. The graph should be created using the first two strings. The characters of the third string S simply denotes where the traversal of this graph should begin. The root or the searched value of this graph is the lexicographically smallest character in the graph.

Details:

The graphs can be created in two ways.

• The first method is using simple undirected graphs with DFS or BFS. For each characters of S, the smallest character in its graph can be searched.
• The second method is using the Disjoint-set data structure. The root of each set should be smallest character. For each characters of S, we simply pick its root.