当前位置:网站首页>Simulation volume leetcode [general] 1061 Arrange the smallest equivalent strings in dictionary order
Simulation volume leetcode [general] 1061 Arrange the smallest equivalent strings in dictionary order
2022-07-06 06:17:00 【Encounter simulation volume】
Summary : Simulation volume Leetcode Summary of questions
1061. The smallest equivalent string in lexicographic order
Give two strings of the same length s1 and s2 , There is also a string baseStr .
among s1[i] and s2[i] It's a set of equivalent characters .
for instance , If s1 = “abc” And s2 = “cde”, Then there is ‘a’ == ‘c’, ‘b’ == ‘d’, ‘c’ == ‘e’.
Equivalent characters follow the general rules of any equivalence relationship :
reflexivity :‘a’ == ‘a’
symmetry :‘a’ == ‘b’ There must be ‘b’ == ‘a’
Transitivity :‘a’ == ‘b’ And ‘b’ == ‘c’ That means ‘a’ == ‘c’
for example , s1 = “abc” and s2 = “cde” The equivalent information is the same as in the previous example , that baseStr = “eed” , “acd” or “aab”, All three strings are equivalent , and “aab” yes baseStr The smallest equivalent string in dictionary order
utilize s1 and s2 The equivalent information of , Find out and return to baseStr The smallest equivalent string in lexicographic order .
Example 1:
Input :s1 = “parker”, s2 = “morris”, baseStr = “parser”
Output :“makkek”
explain : according to A and B Equivalent information in , We can divide these characters into [m,p], [a,o], [k,r,s], [e,i] common 4 Group . The characters in each group are equivalent , And in dictionary order . So the answer is “makkek”.
Example 2:
Input :s1 = “hello”, s2 = “world”, baseStr = “hold”
Output :“hdld”
explain : according to A and B Equivalent information in , We can divide these characters into [h,w], [d,e,o], [l,r] common 3 Group . So only S The second character in ‘o’ become ‘d’, The final answer is “hdld”.
Example 3:
Input :s1 = “leetcode”, s2 = “programs”, baseStr = “sourcecode”
Output :“aauaaaaada”
explain : We can A and B The equivalent characters in are divided into [a,o,e,r,s,c], [l,p], [g,t] and [d,m] common 4 Group , therefore S In addition to ‘u’ and ‘d’ All the other letters are converted into ‘a’, The final answer is “aauaaaaada”.
Tips :
1 <= s1.length, s2.length, baseStr <= 1000
s1.length == s2.length
character string s1, s2, and baseStr Only from ‘a’ To ‘z’ The lowercase letters of .
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/lexicographically-smallest-equivalent-string
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Code :
import string
from leetcode_python.utils import *
class UnionFindSet(object):
""" Union checking set """
def __init__(self, data_list):
""" Initialize two dictionaries , A parent node that saves nodes , Another one saves the size of the parent node When initializing , Set the parent node of the node as itself ,size Set to 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):
""" Use recursion to find the parent node When finding the parent node , By the way, move the current node to the parent node This operation is an optimization """
father = self.parent_dict[node]
if(node != father):
if father != self.parent_dict[father]: # When reducing tree height optimization , Ensure that the parent node size dictionary is correct
self.size_dict[father] -= 1
father = self.find(father)
self.parent_dict[node] = father
return father
def isConnected(self, node_a, node_b):
""" Check whether the two nodes are in the same set """
return self.find(node_a) == self.find(node_b)
def union(self, node_a, node_b):
""" Merge the two sets together """
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 turn 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')
remarks :
GitHub:https://github.com/monijuan/leetcode_python
CSDN Summary : Simulation volume Leetcode Summary of questions
You can add QQ Group communication :1092754609
leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ! thank you !
边栏推荐
- [postman] collections configuration running process
- Understanding of processes and threads
- [API interface tool] Introduction to postman interface
- Function of contenttype
- F - True Liars (种类并查集+DP)
- 模拟卷Leetcode【普通】1062. 最长重复子串
- Customize the gateway filter factory on the specified route
- Full link voltage measurement: building three models
- 数学三大核心领域概述:几何
- Digital triangle model acwing 1015 Picking flowers
猜你喜欢
F - True Liars (种类并查集+DP)
sourceInsight中文乱码
Full link voltage measurement: building three models
Isam2 operation process
Pat (Grade B) 2022 summer exam
On weak network test of special test
Hypothesis testing learning notes
Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
在uni-app中使用腾讯视频插件播放视频
LeetCode 729. 我的日程安排表 I
随机推荐
数据库隔离级别
Hypothesis testing learning notes
selenium源码通读·9 |DesiredCapabilities类分析
Construction and integration of Zipkin and sleuth for call chain monitoring
E - food chain
MySQL之数据类型
B - The Suspects
单元测试的意义
LeetCode 729. 我的日程安排表 I
全链路压测:构建三大模型
【Postman】测试(Tests)脚本编写和断言详解
PAT(乙级)2022年夏季考试
模拟卷Leetcode【普通】1062. 最长重复子串
Basic knowledge of error
还在为如何编写Web自动化测试用例而烦恼嘛?资深测试工程师手把手教你Selenium 测试用例编写
【Postman】Collections配置运行过程
这些年用Keil遇到的坑
浅谈专项测试之弱网络测试
B - The Suspects
Eigen sparse matrix operation