diff options
author | Jack Sangdahl <[email protected]> | 2025-06-04 18:29:40 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-04 18:29:40 -0600 |
commit | a05784326180667fd695dd35d97dce314ab0a31c (patch) | |
tree | a9f0c59d9d7078ab5f44dfb333e9807930ff771c /lexicographically_smallest_equivalent_str.py | |
parent | bc5339f3d4c2251937712cbe65bed32f2e0ab5b6 (diff) | |
download | leetcode-a05784326180667fd695dd35d97dce314ab0a31c.tar.gz leetcode-a05784326180667fd695dd35d97dce314ab0a31c.zip |
1061. lexicographically smallest equivalent string
Diffstat (limited to 'lexicographically_smallest_equivalent_str.py')
-rw-r--r-- | lexicographically_smallest_equivalent_str.py | 49 |
1 files changed, 49 insertions, 0 deletions
diff --git a/lexicographically_smallest_equivalent_str.py b/lexicographically_smallest_equivalent_str.py new file mode 100644 index 0000000..534d844 --- /dev/null +++ b/lexicographically_smallest_equivalent_str.py @@ -0,0 +1,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") + ) |