1061. Lexicographically Smallest Equivalent String¶
题目信息¶
- 题号:
1061
- 难度:
Medium
- 主题:
字符等价关系、传递闭包、字典序最小化
- 原题:
- 重点:
s1[i]与s2[i]建立的等价关系具有自反、对称和传递性;baseStr每个字符可独立替换为任意等价字符
题目重述¶
给定长度相同的小写字符串 s1 和 s2。对于每个下标 i,规定字符 s1[i] 与 s2[i] 等价。字符与自身等价,等价关系可以双向使用,并且具有传递性。
另给定字符串 baseStr。可以把其中每个字符替换为与它等价的任意小写字母。请返回所有可得到字符串中字典序最小的一个;各位置的替换选择互不影响。
1 <= s1.length == s2.length <= 1000,1 <= baseStr.length <= 1000,所有字符串只包含小写英文字母。
自建示例¶
传递关系把多个字符合并为同一等价类:
输入:s1 = "abc", s2 = "bcd", baseStr = "dad"
输出:"aaa"
解释:a、b、c、d 通过三组关系全部等价,因此 baseStr 中的 d 和 a 都可以替换为该等价类中字典序最小的 a。
字符不属于任何非平凡等价类:
输入:s1 = "a", s2 = "b", baseStr = "cz"
输出:"cz"
解释:c 和 z 只与自身等价,无法替换为更小字符,因此结果保持不变。