LeetCode 题解工作台
按字典序排列最小的等效字符串
给出长度相同的两个字符串 s1 和 s2 ，还有一个字符串 baseStr 。 其中 s1[i] 和 s2[i] 是一组等价字符。 举个例子，如果 s1 = "abc" 且 s2 = "cde" ，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e' 。 等价字符遵循任何等…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 并查集
答案摘要
我们可以使用并查集来处理等价字符的关系。每个字符可以看作一个节点，等价关系可以看作是连接这些节点的边。通过并查集，我们可以将所有等价的字符归为一类，并且在查询时能够快速找到每个字符的代表元素。我们在进行合并操作时，始终将代表元素设置为字典序最小的字符，这样可以确保最终得到的字符串是按字典序排列的最小等价字符串。 时间复杂度 $O((n + m) \times \log |\Sigma|)$，空间复…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 并查集 题型思路
题目描述
给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。
其中 s1[i] 和 s2[i] 是一组等价字符。
- 举个例子，如果
s1 = "abc"且s2 = "cde"，那么就有'a' == 'c', 'b' == 'd', 'c' == 'e'。
等价字符遵循任何等价关系的一般规则：
- 自反性 ：
'a' == 'a' - 对称性 ：
'a' == 'b'则必定有'b' == 'a' - 传递性 ：
'a' == 'b'且'b' == 'c'就表明'a' == 'c'
例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串
利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。
示例 1：
输入：s1 = "parker", s2 = "morris", baseStr = "parser" 输出："makkek" 解释：根据A和B中的等价信息，我们可以将这些字符分为[m,p],[a,o],[k,r,s],[e,i]共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是"makkek"。
示例 2：
输入：s1 = "hello", s2 = "world", baseStr = "hold" 输出："hdld" 解释：根据A和B中的等价信息，我们可以将这些字符分为[h,w],[d,e,o],[l,r]共 3 组。所以只有 S 中的第二个字符'o'变成'd'，最后答案为"hdld"。
示例 3：
输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode" 输出："aauaaaaada" 解释：我们可以把A和B中的等价字符分为[a,o,e,r,s,c],[l,p],[g,t]和[d,m]共 4 组，因此S中除了'u'和'd'之外的所有字母都转化成了'a'，最后答案为"aauaaaaada"。
提示：
1 <= s1.length, s2.length, baseStr <= 1000s1.length == s2.length- 字符串
s1,s2, andbaseStr仅由从'a'到'z'的小写英文字母组成。
解题思路
方法一：并查集
我们可以使用并查集来处理等价字符的关系。每个字符可以看作一个节点，等价关系可以看作是连接这些节点的边。通过并查集，我们可以将所有等价的字符归为一类，并且在查询时能够快速找到每个字符的代表元素。我们在进行合并操作时，始终将代表元素设置为字典序最小的字符，这样可以确保最终得到的字符串是按字典序排列的最小等价字符串。
时间复杂度 ，空间复杂度 。其中 是字符串 和 的长度，而 是字符串 的长度，而 是字符集的大小，本题中 。
class Solution:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(26))
for a, b in zip(s1, s2):
x, y = ord(a) - ord("a"), ord(b) - ord("a")
px, py = find(x), find(y)
if px < py:
p[py] = px
else:
p[px] = py
return "".join(chr(find(ord(c) - ord("a")) + ord("a")) for c in baseStr)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N + M*α(N)) where N is the length of baseStr and M is the length of s1/s2 due to union find operations with path compression. Space complexity is O(26) for storing parent pointers for each lowercase character. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate recognizes transitive equivalence and applies union find correctly.
- question_mark
Candidate ensures lexicographical order is maintained in equivalence groups.
- question_mark
Candidate efficiently transforms baseStr without redundant lookups.
常见陷阱
外企场景- error
Failing to merge equivalence groups correctly and violating transitive relations.
- error
Replacing characters without considering the smallest lexicographical representative.
- error
Overcomplicating union find by not taking advantage of the small fixed alphabet.
进阶变体
外企场景- arrow_right_alt
Apply the same approach to uppercase letters or extended Unicode characters.
- arrow_right_alt
Find the largest lexicographical equivalent string instead of the smallest.
- arrow_right_alt
Compute equivalence only for a subset of characters in baseStr.