跳到主要内容

839.相似字符串组

链接:839.相似字符串组
难度:Hard
标签:深度优先搜索、广度优先搜索、并查集、数组、哈希表、字符串
简介:如果交换字符串 X 中的两个不同位置的字母,使得它和字符串 Y 相等,那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的,那它们也是相似的。给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组?。

题解 1 - typescript

  • 编辑时间:2021-02-01
  • 执行用时:108ms
  • 内存消耗:43.2MB
  • 编程语言:typescript
  • 解法介绍:利用并查集整合组。
class UnionFind {
elements: number[];
constructor(public size: number) {
this.elements = new Array(size).fill(0).map((_, i) => i);
}
same(v1: number, v2: number): boolean {
return this.find(v1) === this.find(v2);
}
find(v: number): number {
return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
}
union(v1: number, v2: number): void {
const e1 = this.find(v1);
const e2 = this.find(v2);
if (e1 !== e2) {
this.elements[e1] = e2;
this.size--;
}
}
}
function numSimilarGroups(strs: string[]): number {
const len = strs.length;
const charLen = strs[0].length;
const check = (str1: string, str2: string) => {
let num = 0;
for (let i = 0; i < charLen; i++) {
if (str1[i] !== str2[i] && ++num > 2) return false;
}
return true;
};
const uf = new UnionFind(len);
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++) {
const str1 = strs[i];
const str2 = strs[j];
if (check(str1, str2)) {
uf.union(i, j);
}
}
}
return uf.size;
}