Simulation volume leetcode [general] 1061 Arrange the smallest equivalent strings in dictionary order

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 ！