当前位置:网站首页>模拟卷Leetcode【普通】1061. 按字典序排列最小的等效字符串
模拟卷Leetcode【普通】1061. 按字典序排列最小的等效字符串
2022-07-06 06:15:00 【邂逅模拟卷】
汇总:模拟卷Leetcode 题解汇总
1061. 按字典序排列最小的等效字符串
给出长度相同的两个字符串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 <= 1000
s1.length == s2.length
字符串s1, s2, and baseStr 仅由从 ‘a’ 到 ‘z’ 的小写英文字母组成。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lexicographically-smallest-equivalent-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
代码:
import string
from leetcode_python.utils import *
class UnionFindSet(object):
"""并查集"""
def __init__(self, data_list):
"""初始化两个字典,一个保存节点的父节点,另外一个保存父节点的大小 初始化的时候,将节点的父节点设为自身,size设为1"""
self.parent_dict = {
}
self.size_dict = {
}
for node in data_list:
self.parent_dict[node] = node
self.size_dict[node] = 1
def find(self, node):
"""使用递归的方式来查找父节点 在查找父节点的时候,顺便把当前节点移动到父节点上面 这个操作算是一个优化 """
father = self.parent_dict[node]
if(node != father):
if father != self.parent_dict[father]: # 在降低树高优化时,确保父节点大小字典正确
self.size_dict[father] -= 1
father = self.find(father)
self.parent_dict[node] = father
return father
def isConnected(self, node_a, node_b):
"""查看两个节点是不是在一个集合里面"""
return self.find(node_a) == self.find(node_b)
def union(self, node_a, node_b):
"""将两个集合合并在一起"""
if node_a is None or node_b is None:
return
a_head = self.find(node_a)
b_head = self.find(node_b)
if(a_head != b_head):
a_set_size = self.size_dict[a_head]
b_set_size = self.size_dict[b_head]
if(a_head < b_head):
self.parent_dict[b_head] = a_head
self.size_dict[a_head] = a_set_size + b_set_size
else:
self.parent_dict[a_head] = b_head
self.size_dict[b_head] = a_set_size + b_set_size
class Solution:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
unionset = UnionFindSet(string.ascii_lowercase)
for c1,c2 in zip(s1,s2): unionset.union(c1,c2)
return ''.join(unionset.find(c)for c in baseStr)
def test(data_test):
s = Solution()
data = data_test # normal
# data = [list2node(data_test[0])] # list转node
return s.smallestEquivalentString(*data)
def test_obj(data_test):
result = [None]
obj = Solution(*data_test[1][0])
for fun, data in zip(data_test[0][1::], data_test[1][1::]):
if data:
res = obj.__getattribute__(fun)(*data)
else:
res = obj.__getattribute__(fun)()
result.append(res)
return result
if __name__ == '__main__':
datas = [
["parker","morris","parser"],
]
for data_test in datas:
t0 = time.time()
print('-' * 50)
print('input:', data_test)
print('output:', test(data_test))
print(f'use time:{
time.time() - t0}s')
备注:
GitHub:https://github.com/monijuan/leetcode_python
CSDN汇总:模拟卷Leetcode 题解汇总
可以加QQ群交流:1092754609
leetcode_python.utils详见汇总页说明
先刷的题,之后用脚本生成的blog,如果有错请留言,我看到了会修改的!谢谢!
边栏推荐
- Linux regularly backs up MySQL database
- Eigen稀疏矩阵操作
- Luogu p1460 [usaco2.1] healthy Holstein cows
- 进程和线程的理解
- Still worrying about how to write web automation test cases? Senior test engineers teach you selenium test case writing hand in hand
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- Significance of unit testing
- GTSAM中李群的運用
- E - food chain
- sourceInsight中文乱码
猜你喜欢
LeetCode 739. 每日温度
Database - current read and snapshot read
properties文件
(中)苹果有开源,但又怎样呢?
Manhattan distance sum - print diamond
[wechat applet] build a development tool environment
[postman] collections - run the imported data file of the configuration
Detailed explanation of BF and KMP
误差的基本知识
Function of contenttype
随机推荐
How to extract login cookies when JMeter performs interface testing
假设检验学习笔记
《卓有成效的管理者》读书笔记
Réflexions sur la sécurité des données (réimpression)
GTSAM中李群的運用
Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
浅谈专项测试之弱网络测试
曼哈顿距离和-打印菱形
Isam2 operation process
JMeter做接口测试,如何提取登录Cookie
异常检测方法总结
[leetcode] day96 - the first unique character & ransom letter & letter ectopic word
[postman] dynamic variable (also known as mock function)
E - 食物链
LeetCode 732. 我的日程安排表 III
Testing of web interface elements
selenium源码通读·9 |DesiredCapabilities类分析
【Tera Term】黑猫带你学TTL脚本——嵌入式开发中串口自动化神技能
JWT-JSON WEB TOKEN
Software test interview questions - Test Type