Sponsored
Sponsored
The idea is to use a union-find data structure to record the equivalence relationships between characters. The union operation will merge sets of equivalent characters.
Next, for each character, we find its representative in the equivalence class (or set), and map each character to the lexicographically smallest character in its set, thus ensuring the smallest equivalent transformation.
Time Complexity: O(N + M), where N is the length of s1 and s2, and M is the length of baseStr.
Space Complexity: O(ALPHABET_SIZE), which is constant due to the fixed size of the alphabet.
1using System;
2
3class Solution {
4 public string SmallestEquivalentString(string s1, string s2, string baseStr) {
5 int[] parent = new int[26];
6 for (int i = 0; i < 26; i++)
7 parent[i] = i;
8
9 for (int i = 0; i < s1.Length; i++) {
10 Union(parent, s1[i] - 'a', s2[i] - 'a');
11 }
12
13 for (int i = 0; i < 26; i++)
14 parent[i] = Find(parent, i);
15
16 char[] result = new char[baseStr.Length];
17 for (int i = 0; i < baseStr.Length; i++) {
18 result[i] = (char)(parent[baseStr[i] - 'a'] + 'a');
19 }
20
21 return new string(result);
22 }
23
24 private int Find(int[] parent, int x) {
25 if (parent[x] != x)
26 parent[x] = Find(parent, parent[x]);
27 return parent[x];
28 }
29
30 private void Union(int[] parent, int x, int y) {
31 int rootX = Find(parent, x);
32 int rootY = Find(parent, y);
33 if (rootX != rootY)
34 parent[Math.Max(rootX, rootY)] = Math.Min(rootX, rootY);
35 }
36
37 static void Main(string[] args) {
38 Solution sol = new Solution();
39 Console.WriteLine(sol.SmallestEquivalentString("parker", "morris", "parser")); // Output: "makkek"
40 }
41}This C# implementation keeps track of equivalence classes using a union-find structure. The characters are merged by `Union` into equivalent sets, and each character from `baseStr` is replaced by the smallest character in its equivalence class to form the result.
Another method is treating each character as a node in a graph where edges connect equivalent nodes (characters). Perform Depth-First Search (DFS) to find all characters that belong to an equivalence group.
Once we have gathered all groups and established the smallest character for each group, we can form the desired output by mapping each baseStr character to the smallest in its equivalence class.
Time Complexity: O(N + M), where N is the length of s1 and s2, and M is the number of edges in the graph (size of baseStr).
Space Complexity: O(ALPHABET_SIZE), due to the storage of graph nodes and mappings.
1def build_graph(s1, s2):
2 graph = {chr(
This Python function constructs a graph from the equivalences given in s1 and s2. It then performs DFS to determine the connected components of the graph, which represent equivalence classes. After identifying each group, it maps all characters in the group to their minimum character to construct the smallest equivalent string for baseStr.