-
Notifications
You must be signed in to change notification settings - Fork 0
/
1061.py
63 lines (47 loc) · 1.67 KB
/
1061.py
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from collections import defaultdict
from utils import assert_solvers
class SolutionUnionFind:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
union_find = {}
def find(u: str):
union_find.setdefault(u, u)
if u != union_find[u]:
union_find[u] = find(union_find[u])
return union_find[u]
def union(u: str, q: str):
ru, rq = find(u), find(q)
if ru < rq:
union_find[rq] = ru
else:
union_find[ru] = rq
for c1, c2 in zip(s1, s2):
union(c1, c2)
return ''.join([find(ch) for ch in baseStr])
class SolutionSets:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
eq_dict = defaultdict(set)
for c1, c2 in zip(s1, s2):
eq_dict[c1].add(c1)
eq_dict[c1].add(c2)
eq_dict[c2].add(c1)
eq_dict[c2].add(c2)
for k, v in eq_dict.items():
for ch in v:
eq_dict[ch].update(v)
sorted_dict = defaultdict(list)
for k, v in eq_dict.items():
sorted_dict[k] = sorted(v)
ans = ''
for ch in baseStr:
if ch in sorted_dict:
ans += sorted_dict[ch][0]
else:
ans += ch
return ans
if __name__ == '__main__':
solvers = [SolutionSets().smallestEquivalentString, SolutionUnionFind().smallestEquivalentString]
test_inputs = [
(("parker", "morris", "parser"), "makkek"),
(("leetcode", "programs", "sourcecode"), "aauaaaaada"),
]
assert_solvers(solvers, test_inputs)