当前位置：首页 > article >正文

剑指 Offer II 117. 相似的字符串

article 2025/3/26 16:40:18

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20117.%20%E7%9B%B8%E4%BC%BC%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2/README.md

剑指 Offer II 117. 相似的字符串

题目描述

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给定一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个 字母异位词 。请问 strs 中有多少个相似字符串组？

字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

示例 1：

输入：strs = ["tars","rats","arts","star"]
输出：2

示例 2：

输入：strs = ["omv","ovm"]
输出：1

提示：

1 <= strs.length <= 300
1 <= strs[i].length <= 300
strs[i] 只包含小写字母。
strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

注意：本题与主站 839 题相同：https://leetcode.cn/problems/similar-string-groups/

解法

并查集
把每个字符串看作是图中的节点，若两个字符串相似，那么它们对应的节点之间存在一条边，也就属于同一个子图。实际上，本问题与面试题116 是非常相似的，一个是学生之间的朋友关系，一个是关于字符串的相似关系。另外本题中两个字符串的相似关系需要自行判断，可以使用一个函数 isAnagram 进行判断。因为题目中明确表示 “strs 中的所有单词都具有相同的长度，且是彼此的字母异位词” ，所以只需统计两个字符串中相同位置的不同字符的个数，若不同的字符个数为 0 或者 2 则（不可能为单数）那么两个字符串就是相似的。完整的代码如下，总的时间复杂度为 O(n^2)。

方法一

Python3

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        #

        n=len(strs)
        fa={}
        ct={}
        for s in strs:
            fa[s]=s
            ct[s]=1

        def find(x: int) -> int:
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]
        def union(x: int, y: int) -> None:
            xp,yp=find(x),find(y)
            fa[xp]=yp
            ct[yp]+=ct[xp]
            ct[xp]=0  #【注意】这里会将相同字符串key对应的cnt都置为0，比如{'abc': 'abc'} {'abc': 0}
            
        
        def is_similar(x: str, y: str) -> bool:
            cnt=0
            for c,m in zip(x,y):
                if c!=m:
                    cnt+=1
                    if cnt>2:return  #能大幅减少均摊复杂度
            return cnt==0 or cnt==2

        # 检查所有可能的字符串对是否相似
        for i in range(n):
            for j in range(i + 1, n):
                x,y=strs[i], strs[j]
                if is_similar(x,y):
                    union(x, y)

        # 统计根节点的数量
        print(fa,ct)
        return len(set(find(x)  for x in strs))  #最保险的写法

Java

class Solution {
    private int[] p;

    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (check(strs[i], strs[j])) {
                    p[find(i)] = find(j);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (i == find(i)) {
                ++res;
            }
        }
        return res;
    }

    private boolean check(String a, String b) {
        int cnt = 0;
        int n = a.length();
        for (int i = 0; i < n; ++i) {
            if (a.charAt(i) != b.charAt(i)) {
                ++cnt;
            }
        }
        return cnt <= 2;
    }

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

C++

class Solution {
public:
    vector<int> p;

    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        p.resize(n);
        for (int i = 0; i < n; ++i) p[i] = i;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (check(strs[i], strs[j]))
                    p[find(i)] = find(j);
        int ans = 0;
        for (int i = 0; i < n; ++i)
            if (i == find(i))
                ++ans;
        return ans;
    }

    bool check(string a, string b) {
        int cnt = 0;
        for (int i = 0; i < a.size(); ++i)
            if (a[i] != b[i])
                ++cnt;
        return cnt <= 2;
    }

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
};

Go

func numSimilarGroups(strs []string) int {
	n := len(strs)
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	check := func(a, b string) bool {
		cnt := 0
		for i := range a {
			if a[i] != b[i] {
				cnt++
			}
		}
		return cnt <= 2
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if check(strs[i], strs[j]) {
				p[find(i)] = find(j)
			}
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		if i == find(i) {
			ans++
		}
	}
	return ans
}

Swift

class Solution {
    private var parent: [Int] = []

    func numSimilarGroups(_ strs: [String]) -> Int {
        let n = strs.count
        parent = Array(0..<n)

        for i in 0..<n {
            for j in (i + 1)..<n {
                if check(strs[i], strs[j]) {
                    parent[find(i)] = find(j)
                }
            }
        }

        var groups = 0
        for i in 0..<n {
            if i == find(i) {
                groups += 1
            }
        }
        return groups
    }

    private func check(_ a: String, _ b: String) -> Bool {
        let n = a.count
        var count = 0
        let arrA = Array(a), arrB = Array(b)

        for i in 0..<n {
            if arrA[i] != arrB[i] {
                count += 1
            }
            if count > 2 {
                return false
            }
        }
        return count <= 2
    }

    private func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
}