模拟卷Leetcode【普通】1061. 按字典序排列最小的等效字符串

汇总：模拟卷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，如果有错请留言，我看到了会修改的！谢谢！