# Lexicographically Smallest Equivalent String

```
Given strings A and B of the same length, we say A[i] and B[i] are equivalent characters. For example, if A = "abc" and B = "cde", then we have 'a' == 'c', 'b' == 'd', 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

Reflexivity: 'a' == 'a'
Symmetry: 'a' == 'b' implies 'b' == 'a'
Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'
For example, given the equivalency information from A and B above, S = "eed", "acd", and "aab" are equivalent strings, and "aab" is the lexicographically smallest equivalent string of S.

Return the lexicographically smallest equivalent string of S by using the equivalency information from A and B.



Example 1:

Input: A = "parker", B = "morris", S = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in A and B, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is "makkek".
Example 2:

Input: A = "hello", B = "world", S = "hold"
Output: "hdld"
Explanation:  Based on the equivalency information in A and B, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter 'o' in S is changed to 'd', the answer is "hdld".
Example 3:

Input: A = "leetcode", B = "programs", S = "sourcecode"
Output: "aauaaaaada"
Explanation:  We group the equivalent characters in A and B as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in S except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".


Note:

String A, B and S consist of only lowercase English letters from 'a' - 'z'.
The lengths of string A, B and S are between 1 and 1000.
String A and B are of the same length.
```

分析

把A,B建图，dfs这里就是S里每个c.dfs图，得到最小的c。每个路径一个seen

```
class Solution:
    def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
        g = collections.defaultdict(list)
        for a,b in zip(A,B):
            g[a].append(b)
            g[b].append(a)
        def dfs(c,mn,seen):
            if c in seen:
                return mn
            seen.add(c)
            res = mn
            for n in g[c]:
                if n not in seen:
                    res=min(res,dfs(n,min(mn,n),seen))
            return res
        return ''.join([dfs(c,c,set()) for c in S])
```

UnionFind

```
class Solution:
    def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
        f = {}
        def find(x):
            f.setdefault(x,x)
            if f[x] != x:
                f[x] = find(f[x])
            return f[x]
        def union(x,y):
            fx = find(x)
            fy = find(y)
            if fx < fy:
                f[fy] = fx
            else:
                f[fx] = fy 
        for a,b in zip(A,B):
            union(a,b)

        res = ''
        for c in S:
            res += find(c)

        return res
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/dfs/lexicographically-smallest-equivalent-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.