aboutsummaryrefslogtreecommitdiff
path: root/lexicographically_smallest_equivalent_str.py
diff options
context:
space:
mode:
Diffstat (limited to 'lexicographically_smallest_equivalent_str.py')
-rw-r--r--lexicographically_smallest_equivalent_str.py49
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")
+ )