1061. Lexicographically Smallest Equivalent String

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        Map<Character, Set<Character>> nodeNeighbors = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            char letterOne = s1.charAt(i), letterTwo = s2.charAt(i);
            nodeNeighbors.computeIfAbsent(letterOne, (key) -> new HashSet<>()).add(letterTwo);
            nodeNeighbors.computeIfAbsent(letterTwo, (key) -> new HashSet<>()).add(letterOne);
        }
        Map<Character, Character> letterMinCharMapping = new HashMap<>();
        StringBuilder ans = new StringBuilder();
        for (char letter : baseStr.toCharArray()) {
            if (!nodeNeighbors.containsKey(letter)) {
                ans.append(letter);
                continue;
            }
            if (!letterMinCharMapping.containsKey(letter)) {
                StringBuilder nodes = new StringBuilder();
                char minChar = getMinChar(letter, nodeNeighbors, nodes, new HashSet<>());
                store(letterMinCharMapping, minChar, nodes.toString());
            }
            ans.append(letterMinCharMapping.get(letter));
        }
        return ans.toString();
    }

    private char getMinChar(char letter, Map<Character, Set<Character>> nodeNeighbors, StringBuilder nodes,
            Set<Character> visited) {
        char currMinChar = letter;
        nodes.append(letter);
        for (char neighbor : nodeNeighbors.get(letter)) {
            if (visited.contains(neighbor))
                continue;
            visited.add(neighbor);
            char minChar = getMinChar(neighbor, nodeNeighbors, nodes, visited);
            if (minChar < currMinChar) {
                currMinChar = minChar;
            }
        }
        return currMinChar;
    }

    private void store(Map<Character, Character> letterMinCharMapping, char minChar, String nodes) {
        for (char node : nodes.toCharArray()) {
            letterMinCharMapping.put(node, minChar);
        }
    }
}

每个character看作一个node. 根据s1和s2建立起一个graph. 我们dfs来得到互相连接的nodes中最小的char. 记得用map来存储每个node对应的最小char, 这样遇到相同的node的时候就不需要重新dfs了.

时间复杂度: O(n)
空间复杂度: O(n)

class Solution {
    static class UnionFind {
        private int[] parent;
        private int[] rank;
        private int[] minChar;

        private UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            minChar = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 1;
                minChar[i] = i;
            }
        }

        private int find(int node) {
            if (node == parent[node])
                return node;
            return parent[node] = find(parent[node]);
        }

        private void union(int nodeOne, int nodeTwo) {
            int rootOne = find(nodeOne);
            int rootTwo = find(nodeTwo);
            if (rootOne != rootTwo) {
                if (rank[rootOne] < rank[rootTwo]) {
                    parent[rootOne] = rootTwo;
                    minChar[rootTwo] = Math.min(minChar[rootOne], minChar[rootTwo]);
                } else if (rank[rootOne] > rank[rootTwo]) {
                    parent[rootTwo] = rootOne;
                    minChar[rootOne] = Math.min(minChar[rootOne], minChar[rootTwo]);
                } else {
                    parent[rootTwo] = rootOne;
                    minChar[rootOne] = Math.min(minChar[rootOne], minChar[rootTwo]);
                    rank[rootOne] += 1;
                }
            }
        }
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        UnionFind uf = new UnionFind(26);
        for (int i = 0; i < s1.length(); i++) {
            uf.union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }
        StringBuilder ans = new StringBuilder();
        for (char letter : baseStr.toCharArray()) {
            ans.append((char) (uf.minChar[uf.find(letter - 'a')] + 'a'));
        }
        return ans.toString();
    }
}

用UF更加便捷. 我们此时要记录每个group中的最小char是什么.