Re: [閒聊] 每日LeetCode

[fxfxxxfxx (愛麗絲)]

※ 引述《fxfxxxfxx (愛麗絲)》之銘言：
: 今天的每日一題
: https://i.imgur.com/k8OAIB9.png
: 連題目是什麼都不知道 :)
: 這是要怎麼寫

好像修好了
不過看起來就只是讓這題變不是 premium


1061. Lexicographically Smallest Equivalent String

對所有 i，要讓 A[i] == B[i]

標準的 union find，把 parent 設成最小的那個就可以了
總共只會有 26*26 = 676 種可能的 query
甚至比 s1 的最大長度 1000 還少


    class Solution {
    public:
        vector<int> parent = vector<int>(128);

        int find(int a) {
            if (parent[a] != a)
                parent[a] = find(parent[a]);
            return parent[a];
        }

        void merge(int u, int v) {
            u = find(u);
            v = find(v);
            if (u > v) swap(u, v);
            parent[v] = u;
        }

        string smallestEquivalentString(string s1, string s2, string baseStr) {
            for (int i = 0; i < 128; i++)
                parent[i] = i;
            int n = s1.size();
            for (int i = 0; i < n; i++)
                merge(s1[i], s2[i]);
            for (char& c: baseStr)
                c = find(c);
            return baseStr;
        }
    };

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673660915.A.8BE.html
推 Rushia: 大師
推 NTHUlagka: 大師