[Leetcode 1061] Lexicographically Smallest Equivalent String

Posted on | In | Comments: | Views:

原题说明

Given strings A and B of the same length, we say A[i] and B[i] are equivalent characters. For example, if A = “abc” and B = “cde”, then we have ‘a’ == ‘c’, ‘b’ == ‘d’, ‘c’ == ‘e’.

Equivalent characters follow the usual rules of any equivalence relation:

  • Reflexivity: ‘a’ == ‘a’
  • Symmetry: ‘a’ == ‘b’ implies ‘b’ == ‘a’
  • Transitivity: ‘a’ == ‘b’ and ‘b’ == ‘c’ implies ‘a’ == ‘c’

For example, given the equivalency information from A and B above, S = “eed”, “acd”, and “aab” are equivalent strings, and “aab” is the lexicographically smallest equivalent string of S.

Return the lexicographically smallest equivalent string of S by using the equivalency information from A and B.

Example 1:

Input: A = “parker”, B = “morris”, S = “parser”
Output: “makkek”
Explanation: Based on the equivalency information in A and B, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is “makkek”.

Example 2:

Input: A = “hello”, B = “world”, S = “hold”
Output: “hdld”
Explanation:  Based on the equivalency information in A and B, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter ‘o’ in S is changed to ‘d’, the answer is “hdld”.

Example 3:

Input: A = “leetcode”, B = “programs”, S = “sourcecode”
Output: “aauaaaaada”
Explanation:  We group the equivalent characters in A and B as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in S except ‘u’ and ‘d’ are transformed to ‘a’, the answer is “aauaaaaada”.

Note:

  1. String A, B and S consist of only lowercase English letters from ‘a’ - ‘z’.
  2. The lengths of string A, B and S are between 1 and 1000.
  3. String A and B are of the same length.

解题思路

这道题很多网上解答是用了Union find，实际上并不是最好的方法。
Union find比较适合union与find操作交错的情况，比如Number of Islands II.
但是这里的话，如果使用Union find，需要先进行一系列union操作，然后进行一系列find操作，时间复杂度是O((M + N)log*(M))，近似于O(M + N). 但是实际上直接使用DFS或者BFS遍历，也可以达到O(M + N)的时间复杂度：

  1. 首先遍历A和B，创建一个字母间关联的无向图mapping
  2. 遍历S，对于S中的每一个字母s，在无向图中进行一次DFS（BFS也可以），找寻关联字母中最小的字母，同时用一个unordered_set visited记录遍历到的点。
  3. visited中的点都是与当前字母s关联的，因此对应的最小字母是一样的，用一个unordered_map memo来记录visited中的点与最小字母的对应关系，这样下次遍历到这些点，就不用再做dfs了，直接从memo中查到对应的最小字母即可。

假设A和B的长度是M，S的长度是N，由于mapping中每一个字母（节点）和每一条边遍历了一遍，这是一个O(M)的时间复杂度，创建mapping是O(M)的时间复杂度，遍历S的时间复杂度为O(N)
所以总的时间复杂度是O(2M + N)也是近似于O(M + N)

示例代码 (cpp)

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
class Solution {
    char dfs(unordered_map<char, vector<char>>& mapping, char input, unordered_set<char>& visited) {
        if (visited.count(input) > 0) {
            return input;
        }
        visited.insert(input);
        char ret = input;
        for (const auto ch : mapping[input]) {
            ret = min(ret, dfs(mapping, ch, visited));
        }
        return ret;
    }
public:
    string smallestEquivalentString(string A, string B, string S) {
        unordered_map<char, vector<char>> mapping;
        for (int i = 0; i < A.size(); ++i) {
            mapping[A[i]].push_back(B[i]);
            mapping[B[i]].push_back(A[i]);
        }
        string ret;
        unordered_map<char, char> memo;
        for (const auto s : S) {
            if (memo.count(s) > 0) {
                ret += memo[s];
                continue;
            }
            unordered_set<char> visited;
            const auto min_char = dfs(mapping, s, visited);
            for (const auto ch : visited) {
                memo[ch] = min_char;
            }
            ret += min_char;
        }
        return ret;
    }
};

示例代码 (java)

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
// Union Find
class Solution {
    public String smallestEquivalentString(String A, String B, String S) {
        int[] graph = new int[26];
        for(int i = 0; i < 26; i++) {
            graph[i] = i;
        }
        for(int i = 0; i < A.length(); i++) {
            int a = A.charAt(i) - 'a';
            int b = B.charAt(i) - 'a';
            int end1 = find(graph, b);
            int end2 = find(graph, a);
            if(end1 < end2) {
                graph[end2] = end1;
            } else {
                graph[end1] = end2;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            sb.append((char)('a' + find(graph, c - 'a')));
        }
        return sb.toString();
    }
    
    private int find(int[] graph, int idx) {
        while(graph[idx] != idx) {
            idx = graph[idx];
        }
        return idx;
    }
}

示例代码 (python)

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
class Solution:
    def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
        neighbors = collections.defaultdict(set)
        for a, b in zip(A, B):
            neighbors[a].add(b)
            neighbors[b].add(a)

        memo = {}

        def bfs(ch):
            if ch in memo: return memo[ch]
            res = ch
            seen = set()
            queue = {ch}

            while queue:
                c = queue.pop()
                if c in seen: continue
                seen.add(c)
                res = min(res, c)
                queue |= neighbors[c]

            for v in seen:
                memo[v] = res

            return res
        return ''.join(bfs(c) for c  in S)

复杂度分析

时间复杂度: O(M + N), 假设A和B的长度是M，S的长度是N
空间复杂度: O(M), 即mapping占用的空间

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！

Related Posts
------ 关注公众号：猩猩的乐园 ------