给出长度相同的两个字符串:A
和 B
,其中 A[i] 和 B[i] 是一组等价字符。举个例子,如果 A = "abc"
且 B = "cde"
,那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'
。
等价字符遵循任何等价关系的一般规则:
- 自反性:'a' == 'a'
- 对称性:'a' == 'b' 则必定有 'b' == 'a'
- 传递性:'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'
例如,A
和 B
的等价信息和之前的例子一样,那么 S = "eed"
, "acd"
或 "aab"
,这三个字符串都是等价的,而 "aab"
是 S
的按字典序最小的等价字符串
利用 A
和 B
的等价信息,找出并返回 S
的按字典序排列最小的等价字符串。
示例 1:
输入:A = "parker", B = "morris", S = "parser" 输出:"makkek" 解释:根据A
和B 中的等价信息,
我们可以将这些字符分为[m,p]
,[a,o]
,[k,r,s]
,[e,i] 共 4 组
。每组中的字符都是等价的,并按字典序排列。所以答案是"makkek"
。
示例 2:
输入:A = "hello", B = "world", S = "hold" 输出:"hdld" 解释:根据A
和B 中的等价信息,
我们可以将这些字符分为[h,w]
,[d,e,o]
,[l,r] 共 3 组
。所以只有 S 中的第二个字符'o'
变成'd',最后答案为
"hdld"
。
示例 3:
输入:A = "leetcode", B = "programs", S = "sourcecode" 输出:"aauaaaaada" 解释:我们可以把 A 和 B 中的等价字符分为[a,o,e,r,s,c]
,[l,p]
,[g,t]
和[d,m] 共 4 组
,因此S
中除了'u'
和'd'
之外的所有字母都转化成了'a'
,最后答案为"aauaaaaada"
。
提示:
- 字符串
A
,B
和S
仅有从'a'
到'z'
的小写英文字母组成。 - 字符串
A
,B
和S
的长度在1
到1000
之间。 - 字符串
A
和B
长度相同。
并查集。
模板 1——朴素并查集:
# 初始化,p存储每个点的父节点
p = list(range(n))
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
模板 2——维护 size 的并查集:
# 初始化,p存储每个点的父节点,size只有当节点是祖宗节点时才有意义,表示祖宗节点所在集合中,点的数量
p = list(range(n))
size = [1] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
if find(a) != find(b):
size[find(b)] += size[find(a)]
p[find(a)] = find(b)
模板 3——维护到祖宗节点距离的并查集:
# 初始化,p存储每个点的父节点,d[x]存储x到p[x]的距离
p = list(range(n))
d = [0] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
d[find(a)] = distance
对于本题,套用并查集模板时,将数值较大的祖宗节点指向数值较小的祖宗节点,这样可以保证祖宗节点存放的是本集合的最小值。
class Solution:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
p = list(range(26))
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
for i in range(len(s1)):
a, b = ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')
pa, pb = find(a), find(b)
if pa < pb:
p[pb] = pa
else:
p[pa] = pb
res = []
for a in baseStr:
a = ord(a) - ord('a')
res.append(chr(find(a) + ord('a')))
return ''.join(res)
class Solution {
private int[] p;
public String smallestEquivalentString(String s1, String s2, String baseStr) {
p = new int[26];
for (int i = 0; i < 26; ++i) {
p[i] = i;
}
for (int i = 0; i < s1.length(); ++i) {
int a = s1.charAt(i) - 'a', b = s2.charAt(i) - 'a';
int pa = find(a), pb = find(b);
if (pa < pb) {
p[pb] = pa;
} else {
p[pa] = pb;
}
}
StringBuilder sb = new StringBuilder();
for (char a : baseStr.toCharArray()) {
char b = (char) (find(a - 'a') + 'a');
sb.append(b);
}
return sb.toString();
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
class Solution {
public:
vector<int> p;
string smallestEquivalentString(string s1, string s2, string baseStr) {
p.resize(26);
for (int i = 0; i < 26; ++i)
p[i] = i;
for (int i = 0; i < s1.size(); ++i)
{
int a = s1[i] - 'a', b = s2[i] - 'a';
int pa = find(a), pb = find(b);
if (pa < pb)
p[pb] = pa;
else
p[pa] = pb;
}
string res = "";
for (char a : baseStr)
{
char b = (char)(find(a - 'a') + 'a');
res += b;
}
return res;
}
int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
};
var p []int
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
p = make([]int, 26)
for i := 0; i < 26; i++ {
p[i] = i
}
for i := 0; i < len(s1); i++ {
a, b := int(s1[i]-'a'), int(s2[i]-'a')
pa, pb := find(a), find(b)
if pa < pb {
p[pb] = pa
} else {
p[pa] = pb
}
}
var res []byte
for _, a := range baseStr {
b := byte(find(int(a-'a'))) + 'a'
res = append(res, b)
}
return string(res)
}
func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}