相似字符串组

发表于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

LeetCode每日一题，839. Similar String Groups

先看题目描述

yAb3c9.png

大意就是给定一个字符串列表 strs，让我们返回其中相似字符串组的个数，字符串相似的定义是：有两个字符串 X 和 Y，若交换 X 中两个字母的位置，可以使得 X 和 Y 相等，或者 X 和 Y 本身就相等，那么就可以说 X 和 Y 相似。至于相似字符串组，以 Example1 为例，tars 和 rats 相似，rats 和 arts 相似，那么 tars，rats 和 arts 就构成了一个相似字符串组，虽然 tars 和 arts 并不相似

算法和思路

并查集

这题我们可以当作图论的题来解决，将字符串看作节点，若两字符串相似，就视作两节点之间存在一条边，那么题目就可以看作是给定一张图，让我们求出图中连通分量的个数。我们可以使用并查集来实时维护图的连通性，求出连通分量的个数并返回

算法源码

并查集

代码中把字符串转化成了字符数组来处理，这样可以提高代码的运行效率

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    private int count;

    public int numSimilarGroups(String[] strs) {
        int m = strs.length;
        int n = strs[0].length();
        this.count = m;
        char[][] css = new char[m][n];
        for (int i = 0; i < m; i++) {
            css[i] = strs[i].toCharArray();
        }
        int[] parent = new int[m];
        for (int i = 0; i <m; i++) {
            parent[i] = i;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                if (isSimilar(css[i], css[j])) {
                    union(i, j, parent);
                }
            }
        }
        return this.count;
    }

    private boolean isSimilar(char[] a, char[] b) {
        int cnt = 2;
        int len = a.length;
        char preA = 'a';
        char preB = 'a';
        for (int i = 0; i < len; i++) {
            if (a[i] != b[i]) {
                if (cnt == 2) {
                    preA = a[i];
                    preB = b[i];
                    cnt--;
                } else if (cnt == 1) {
                    if (a[i] != preB || b[i] != preA) {
                        return false;
                    }
                    cnt--;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    private int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }

    private void union(int a, int b, int[] parent) {
        int x = find(a, parent);
        int y = find(b, parent);
        if (x == y) {
            return;
        }
        parent[y] = x;
        this.count--;
    }
}