按字典序排列最小的等效字符串

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' 的小写英文字母组成。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: string smallestEquivalentString(string s1, string s2, string baseStr) { } };

python3 解法, 执行用时: 156 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-15 12:50:26

# BFS
class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:

        def bfs(ele, visit, data_dict):
            min_char = ele
            queue.append(ele)
            while queue:
                top = queue.popleft()
                min_char = min(min_char, top)
                if top not in visit:
                    visit.add(top)
                    for one in data_dict[top]:
                        queue.append(one)
            return min_char

        import collections
        queue = collections.deque()
        data_dict = collections.defaultdict(set)
        for i in range(len(s1)):
            data_dict[s1[i]].add(s2[i])
            data_dict[s2[i]].add(s1[i])    
        res = ""
        for ele in baseStr:
            visit = set()
            res += bfs(ele, visit, data_dict)
        return res

python3 解法, 执行用时: 228 ms, 内存消耗: 15.2 MB, 提交时间: 2023-01-15 12:49:41

# DFS
class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:

        def dfs(ele, res_char, visit, data_dict):
            res_char = min(res_char, ele)
            if ele not in visit:
                visit.add(ele)
                for one in data_dict[ele]:
                    res_char = min(res_char, dfs(one, res_char, visit, data_dict))  # dfs
            return res_char

        import collections
        data_dict = collections.defaultdict(set)
        for i in range(len(s1)):
            data_dict[s1[i]].add(s2[i])
            data_dict[s2[i]].add(s1[i])
        res = ""
        for ele in baseStr:
            visit = set()
            res += dfs(ele, ele, visit, data_dict)
        return res

python3 解法, 执行用时: 64 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-15 12:47:30

class UnionFind:
    def __init__(self, n):
        self.parent = [x for x in range(n)]
    
    #-------- 扁平化
    def Find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.Find(self.parent[x])
        return self.parent[x]
    
    #-------- 由题意。谁小谁当掌门
    def Union(self, x: int, y: int) -> None:
        root_x = self.Find(x)
        root_y = self.Find(y)
        if root_x < root_y:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y

class Solution:
    def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
        UF = UnionFind(26)
        n = len(A)
        for i in range(n):
            x = ord(A[i]) - ord('a')
            y = ord(B[i]) - ord('a')
            UF.Union(x, y)
        res = ""
        for c in S:
            x = ord(c) - ord('a')
            rt = UF.Find(x)
            res += chr(ord('a') + rt)
        return res

python3 解法, 执行用时: 48 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-15 12:47:15

class UnionFind:
    def __init__(self, n):
        self.parent = [x for x in range(n)]
        self.size = [1 for x in range(n)]       #用不到，纯粹就是为了每次默写
        self.n = n
        self.part = n

    def Find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.Find(self.parent[x])
        return self.parent[x]
    
    #-------- 由题意。谁小谁当掌门
    def Union(self, x: int, y: int) -> bool:
        root_x = self.Find(x)
        root_y = self.Find(y)
        if root_x == root_y:
            return False
        if root_x < root_y:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]
        else:
            self.parent[root_x] = root_y
            self.size[root_y] += self.size[root_x]
        self.part -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.Find(x) == self.Find(y)
    def get_part_size(self, x: int) -> int:
        root_x = self.Find(x)
        return self.size[root_x]

class Solution:
    def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
        UF = UnionFind(26)
        n = len(A)
        for i in range(n):
            x = ord(A[i]) - ord('a')
            y = ord(B[i]) - ord('a')
            UF.Union(x, y)
        res = ""
        for c in S:
            x = ord(c) - ord('a')
            rt = UF.Find(x)
            res += chr(ord('a') + rt)
        return res

java 解法, 执行用时: 1 ms, 内存消耗: 39.8 MB, 提交时间: 2023-01-15 12:46:44

class Solution {
    public String smallestEquivalentString(String A, String B, String S) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        int len = A.length();
        char[] ch1 = A.toCharArray();
        char[] ch2 = B.toCharArray();
        for (int i = 0; i < len; i++) {
            int n1 = ch1[i] - 'a';
            int n2 = ch2[i] - 'a';
            union(parent, n1, n2);
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : S.toCharArray()) {
            int root = find(parent, ch - 'a');
            sb.append((char)(root + 'a'));
        }
        return sb.toString();
    }
    private int find(int[] parent, int index) {
        while (parent[index] != index) {
            index = parent[index];
        }
        return index;
    }
    private void union(int[] parent, int index1, int index2) {
        int xset = find(parent, index1);
        int yset = find(parent, index2);
        if (xset != yset) {
            if (xset < yset) {
                parent[yset] = xset;
            } else {
                parent[xset] = yset;
            }
        }
    }
}

java 解法, 执行用时: 1 ms, 内存消耗: 40.1 MB, 提交时间: 2023-01-15 12:46:28

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int n = s1.length();
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        UF uf = new UF(26);
        for (int i = 0; i < n; i++) {
            char ch1 = chs1[i];
            char ch2 = chs2[i];
            uf.union(ch1 - 'a', ch2 - 'a');
        }
        StringBuilder sb = new StringBuilder();
        char[] baseStrArr = baseStr.toCharArray();
        for (char c : baseStrArr) {
            char nc = (char) (uf.findRoot(c - 'a') + 'a');
            sb.append(nc);
        }
        return sb.toString();
    }

    class UF {
        private int[] parent;
        private int count;

        public UF(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            count = n;
        }
        
        public int findRoot(int x) {
            while(parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        
        public boolean connected(int p, int q) {
            int pRoot = findRoot(p);
            int qRoot = findRoot(q);
            return pRoot == qRoot;
        }

        public void union(int p, int q) {
            int pRoot = findRoot(p);
            int qRoot = findRoot(q);
            if (pRoot == qRoot) {
                return;
            }
            if (pRoot < qRoot) {
                parent[qRoot] = pRoot;
            } else {
                parent[pRoot] = qRoot;
            }
            --count;
        }

        public int getCount() {
            return count;
        }
    }
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 6.4 MB, 提交时间: 2023-01-15 12:45:57

class Solution {
public:
    struct DSU {
        vector<int> F;
        int find(int x) {
            if (F[x] != x) F[x] = find(F[x]);
            return F[x];
        }
        void unite(int x, int y) {
            int f1 = find(x);
            int f2 = find(y);
            F[f1] = F[f2] = min(f1, f2);
        }
        DSU() {
            F = vector<int>(26, 0);
            for (int i = 0; i < 26; ++i) F[i] = i;
        };
    };
    DSU dsu;
    Solution() {
        dsu = DSU();
    }
    string smallestEquivalentString(string A, string B, string S) {
        for (int i = 0; i < A.size(); ++i) {
            dsu.unite(A[i] - 'a', B[i] - 'a');
        }
        string res;
        for (auto x : S) {
            res += dsu.find(x - 'a') + 'a';
        }
        return res;
    }
};

上一题

下一题

详情