Given strings A
and B
of the same length, we say A[i] and B[i] are equivalent characters. For example, if A = "abc"
and B = "cde"
, then we have 'a' == 'c', 'b' == 'd', 'c' == 'e'
.
Equivalent characters follow the usual rules of any equivalence relation:
For example, given the equivalency information from A
and B
above, S = "eed"
, "acd"
, and "aab"
are equivalent strings, and "aab"
is the lexicographically smallest equivalent string of S
.
Return the lexicographically smallest equivalent string of S
by using the equivalency information from A
and B
.
Example 1:
Input: A = "parker", B = "morris", S = "parser" Output: "makkek" Explanation: Based on the equivalency information inA
andB
, 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: A = "hello", B = "world", S = "hold" Output: "hdld" Explanation: Based on the equivalency information inA
andB
, we can group their characters as[h,w]
,[d,e,o]
,[l,r]
. So only the second letter'o'
inS
is changed to'd'
, the answer is"hdld"
.
Example 3:
Input: A = "leetcode", B = "programs", S = "sourcecode" Output: "aauaaaaada" Explanation: We group the equivalent characters inA
andB
as[a,o,e,r,s,c]
,[l,p]
,[g,t]
and[d,m]
, thus all letters inS
except'u'
and'd'
are transformed to'a'
, the answer is"aauaaaaada"
.
Note:
A
, B
and S
consist of only lowercase English letters from 'a'
- 'z'
.A
, B
and S
are between 1
and 1000
.A
and B
are of the same length.struct Solution;
struct UnionFind {
parent: Vec<usize>,
n: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
j
} else {
self.parent[i] = self.find(j);
self.parent[i]
}
}
fn union(&mut self, mut i: usize, mut j: usize) {
i = self.find(i);
j = self.find(j);
if i != j {
let min = i.min(j);
self.parent[i] = min;
self.parent[j] = min;
}
}
}
impl Solution {
fn smallest_equivalent_string(a: String, b: String, s: String) -> String {
let a: Vec<usize> = a.bytes().map(|b| (b - b'a') as usize).collect();
let b: Vec<usize> = b.bytes().map(|b| (b - b'a') as usize).collect();
let n = a.len();
let mut uf = UnionFind::new(26);
for i in 0..n {
uf.union(a[i], b[i]);
}
s.bytes()
.map(|c| (uf.find((c - b'a') as usize) as u8 + b'a') as char)
.collect()
}
}
#[test]
fn test() {
let a = "parker".to_string();
let b = "morris".to_string();
let s = "parser".to_string();
let res = "makkek".to_string();
assert_eq!(Solution::smallest_equivalent_string(a, b, s), res);
let a = "hello".to_string();
let b = "world".to_string();
let s = "hold".to_string();
let res = "hdld".to_string();
assert_eq!(Solution::smallest_equivalent_string(a, b, s), res);
let a = "leetcode".to_string();
let b = "programs".to_string();
let s = "sourcecode".to_string();
let res = "aauaaaaada".to_string();
assert_eq!(Solution::smallest_equivalent_string(a, b, s), res);
}