LeetCode高校编程竞赛--按字典序排列最小的等效字符串(并查集)

一、题目大意

  • 具体的说明记不清楚了,大意如下:

    给定两个长度相等的字符串A和B,我们称A和B在相同位置上的两个字符等价,即A[i] == B[i]

    等价字符遵循任何等价关系的一般规则:

    • 自反性:’a’ == ‘a’
    • 对称性:’a’ == ‘b’ 则必定有 ‘b’ == ‘a’
    • 传递性:’a’ == ‘b’ 且 ‘b’ == ‘c’ 就表明 ‘a’ == ‘c’

    举个例子,如果 A = "abc"B = "cde",那么 S = "eed", "acd""aab",这三个字符串都是等价的,而 "aab"S 的按字典序最小的等价字符串。

    利用 AB 的等价信息,找出并返回 S 的按字典序排列最小的等价字符串。

二、分析

  • 比赛时因为紧张,也因为好久不做类似的题目了,没有解出这道题。今天回味这道题才发现是典型的并查集题目。

  • 我们需要对并查集经典实现方法—按秩合并的启发式策略进行改动。

    在《算法导论》中经典实现方式是把并查集森林里的树高作为秩,合并时,把较大秩的根作为较小秩的根的父节点

  • 本题要求我们给出字典序最小的等价字符串,因此我们的策略应该是:

    • 字符的字典序作为秩
    • 合并时,把较小秩的根作为较大秩的根的父节点

三、我的代码

  • 这里给出的是C++语言的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    #include<iostream>
    #include<string>
    #include<vector>

    using namespace std;

    //初始化一个并查集
    //nums[i] = a表示结点 i 所在集合的根结点为 a
    vector<int> makeSet(const int& n) {
    vector<int> nums;
    for(int i = 0; i < n; ++i)
    nums.push_back(i);
    return nums;
    }

    //返回 x 在并查集里的根节点
    int findSet(vector<int>& nums, int x) {
    //直到找到根节点
    while(x != nums[x])
    x = nums[x];
    return x;
    }

    //合并 x, y 所在的集合
    void Union(vector<int>& nums, const int &x, const int &y) {
    int p_x = findSet(nums, x), p_y = findSet(nums, y);
    if(p_x > p_y)
    nums[p_x] = p_y;
    else if(p_x < p_y)
    nums[p_y] = p_x;
    }

    //题目需要我们实现的函数
    string smallestEquivalentString(string A, string B, string S) {
    vector<int> nums = makeSet(26);
    for(int i = 0; i < A.size(); ++i)
    Union(nums, A[i] - 'a', B[i] - 'a');
    for(int i = 0; i < S.size(); ++i)
    S[i] = 'a' + findSet(nums, S[i] - 'a');
    return S;
    }

    int main() {
    string A = "parent", B = "father";
    string S = "preanther";
    cout << smallestEquivalentString(A, B, S) << endl;
    return 0;
    }
------------- 本文结束 感谢您的阅读 -------------

本文标题:LeetCode高校编程竞赛--按字典序排列最小的等效字符串(并查集)

文章作者:Perry

发布时间:2019年04月22日 - 23:03

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/20ed3bc.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%