Algorithm
Problem Name: 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.
- For example, if
s1 = "abc"ands2 = "cde", then we have'a' == 'c','b' == 'd', and'c' == 'e'.
Equivalent characters follow the usual rules of any equivalence relation:
- Reflexivity:
'a' == 'a'. - Symmetry:
'a' == 'b'implies'b' == 'a'. - Transitivity:
'a' == 'b'and'b' == 'c'implies'a' == 'c'.
For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.
Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.
Example 1:
Input: s1 = "parker", s2 = "morris", baseStr = "parser" Output: "makkek" Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is "makkek".
Example 2:
Input: s1 = "hello", s2 = "world", baseStr = "hold" Output: "hdld" Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".
Example 3:
Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode" Output: "aauaaaaada" Explanation: We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".
Constraints:
1 <= s1.length, s2.length, baseStr <= 1000s1.length == s2.lengths1,s2, andbaseStrconsist of lowercase English letters.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String smallestEquivalentString(String s1, String s2, String baseStr) {
int[] graph = new int[26];
for (int i = 0; i < 26; i++) {
graph[i] = i;
}
for (int i = 0; i < s1.length(); i++) {
int idxOne = s1.charAt(i) - 'a';
int idxTwo = s2.charAt(i) - 'a';
int parentOne = find(graph, idxOne);
int parentTwo = find(graph, idxTwo);
if(parentOne < parentTwo) {
graph[parentTwo] = parentOne;
} else {
graph[parentOne] = parentTwo;
}
}
StringBuilder sb = new StringBuilder();
for (char c : baseStr.toCharArray()) {
sb.append((char) ('a' + find(graph, c - 'a')));
}
return sb.toString();
}
private int find(int[] graph, int idx) {
while(graph[idx] != idx> {
idx = graph[idx];
}
return idx;
}
}
Input
s1 = "parker", s2 = "morris", baseStr = "parser"
Output
"makkek"
#2 Code Example with Javascript Programming
Code -
Javascript Programming
var smallestEquivalentString = function (s1, s2, baseStr) {
if (s1.length === 0 || s2.length === 0) return ''
const uf = new UnionFind()
for (let i = 0; i < s1.length; i++) {
uf.union(s1[i], s2[i])
}
let res = ''
for (const ch of baseStr) {
res += uf.find(ch) || ch // some letters don't have connected component
}
return res
}
class UnionFind {
constructor() {
this.parents = new Map()
}
find(x) {
if (this.parents.get(x) === x) return x
this.parents.set(x, this.find(this.parents.get(x))) // path compression
return this.parents.get(x)
}
union(u, v) {
// init
if (!this.parents.has(u)) {
this.parents.set(u, u)
}
if (!this.parents.has(v)) {
this.parents.set(v, v)
}
// find root
const rootU = this.find(u)
const rootV = this.find(v)
if (rootU === rootV) return // connected already
// set smallest lex as the root
if (rootU > rootV) {
this.parents.set(rootU, rootV)
} else {
this.parents.set(rootV, rootU)
}
}
}
Input
s1 = "parker", s2 = "morris", baseStr = "parser"
Output
"makkek"
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
def root(c):
return c if parent[c] == c else root(parent[c])
parent = {s: s for s in string.ascii_lowercase}
for a, b in zip(A, B):
p1, p2 = root(a), root(b)
if p1 <= p2:
parent[p2] = p1
else:
parent[p1] = p2
return ''.join(root(s) for s in S)
Input
s1 = "hello", s2 = "world", baseStr = "hold"
Output
"hdld"
#4 Code Example with C# Programming
Code -
C# Programming
using System.Text;
namespace LeetCode
{
public class _1061_LexicographicallySmallestEquivalentString
{
public string SmallestEquivalentString(string A, string B, string S)
{
var uf = new UnionFind(26);
for (int i = 0; i < A.Length; i++)
uf.Union(A[i] - 'a', B[i] - 'a');
var sb = new StringBuilder(S.Length);
foreach (var ch in S)
sb.Append((char)(uf.Find(ch - 'a') + 'a'));
return sb.ToString();
}
private class UnionFind
{
private readonly int[] parents;
public UnionFind(int count)
{
this.parents = new int[count];
for (int i = 0; i < count; i++)
parents[i] = i;
}
public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);
return parents[index];
}
public void Union(int index1, int index2)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);
if (pIndex1 == pIndex2) return;
if (pIndex1 < pIndex2)
parents[pIndex2] = pIndex1;
else
parents[pIndex1] = pIndex2;
}
}
}
}
Input
s1 = "hello", s2 = "world", baseStr = "hold"
Output
"hdld"