aboutsummaryrefslogtreecommitdiff
path: root/lexicographically_smallest_equivalent_str.py
blob: 534d84444390f09f6b0ae1be453115427b7bba11 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 1061. Lexicographically Smallest Equivalent String

"""
you are given two strings of the same length 's1' and 's2' and a string
'baseStr'. we say 's1[i]' and 's2[i]' are equivalent characters. equivalent
characters follow the usual rules of any equivalence relation: reflexivity,
symmetry, and transitivity. return the lexicographically smallest equivalent
string of 'baseStr' by using the equivalency information from 's1' and 's2'.
"""


class Solution(object):
    def smallestEquivalentString(self, s1, s2, baseStr):
        """
        :type s1: str
        :type s2: str
        :type baseStr: str
        :rtype: str
        """
        uf = {}

        def find(x):
            uf.setdefault(x, x)
            if x != uf[x]:
                uf[x] = find(uf[x])
            return uf[x]

        def union(x, y):
            rx, ry = find(x), find(y)
            if rx > ry:
                uf[rx] = ry
            else:
                uf[ry] = rx

        for i in range(len(s1)):
            union(s1[i], s2[i])
        ans = []
        for i in baseStr:
            ans.append(find(i))
        return "".join(ans)


if __name__ == "__main__":
    obj = Solution()
    print(obj.smallestEquivalentString(s1="parker", s2="morris", baseStr="parser"))
    print(obj.smallestEquivalentString(s1="hello", s2="world", baseStr="hold"))
    print(
        obj.smallestEquivalentString(s1="leetcode", s2="programs", baseStr="sourcecode")
    )