839. Similar String Groups
Две строки, X и Y, считаются похожими, если либо они идентичны, либо мы можем сделать их эквивалентными, поменяв местами не более двух букв (в разных позициях) в строке X.
Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.
Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?
Пример:
Input: strs = ["tars","rats","arts","star"]
Output: 2
C# решение
сопоставлено/оригиналpublic class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
public class Solution {
public bool IsSimilar(string a, string b) {
int diff = 0;
for (int i = 0; i < a.Length; ++i) {
if (a[i] != b[i]) {
diff++;
}
}
return diff == 0 || diff == 2;
}
public int NumSimilarGroups(string[] strs) {
int n = strs.Length;
UnionFind dsu = new UnionFind(n);
int count = n;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (IsSimilar(strs[i], strs[j]) && dsu.Find(i) != dsu.Find(j)) {
count--;
dsu.Union(i, j);
}
}
}
return count;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class UnionFind {
private vector<int>& parent;
private vector<int>& rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
class Solution {
public:
public bool IsSimilar(string a, string b) {
int diff = 0;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != b[i]) {
diff++;
}
}
return diff == 0 || diff == 2;
}
public int NumSimilarGroups(vector<string> strs) {
int n = strs.size();
UnionFind dsu = new UnionFind(n);
int count = n;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (IsSimilar(strs[i], strs[j]) && dsu.Find(i) != dsu.Find(j)) {
count--;
dsu.Union(i, j);
}
}
}
return count;
}
}Java решение
сопоставлено/оригиналclass UnionFind {
int[] parent;
int[] rank;
public UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++)
parent[i] = i;
rank = new int[size];
}
public int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
public void union_set(int x, int y) {
int xset = find(x), yset = find(y);
if (xset == yset) {
return;
} else if (rank[xset] < rank[yset]) {
parent[xset] = yset;
} else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
} else {
parent[yset] = xset;
rank[xset]++;
}
}
}
class Solution {
public boolean isSimilar(String a, String b) {
int diff = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
diff++;
}
}
return diff == 0 || diff == 2;
}
public int numSimilarGroups(String[] strs) {
int n = strs.length;
UnionFind dsu = new UnionFind(n);
int count = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isSimilar(strs[i], strs[j]) && dsu.find(i) != dsu.find(j)) {
count--;
dsu.union_set(i, j);
}
}
}
return count;
}
}JavaScript решение
сопоставлено/оригиналclass UnionFind {
constructor(size) {
this.parent = Array.from({ length: size }, (_, i) => i);
this.rank = Array(size).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
}
}
const isSimilar = (a, b) => {
let diff = 0;
for (let i = 0; i < a.length; i++) {
if (a[i] !== b[i]) diff++;
}
return diff === 0 || diff === 2;
};
var numSimilarGroups = function(strs) {
const n = strs.length;
const dsu = new UnionFind(n);
let count = n;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (isSimilar(strs[i], strs[j]) && dsu.find(i) !== dsu.find(j)) {
count--;
dsu.union(i, j);
}
}
}
return count;
};Python решение
сопоставлено/оригиналclass UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
class Solution:
def isSimilar(self, a, b):
diff = sum(1 for x, y in zip(a, b) if x != y)
return diff == 0 or diff == 2
def numSimilarGroups(self, strs):
n = len(strs)
dsu = UnionFind(n)
count = n
for i in range(n):
for j in range(i + 1, n):
if self.isSimilar(strs[i], strs[j]) and dsu.find(i) != dsu.find(j):
count -= 1
dsu.union(i, j)
return countGo решение
сопоставлено/оригиналtype UnionFind struct {
parent []int
rank []int
}
func NewUnionFind(size int) *UnionFind {
uf := &UnionFind{
parent: make([]int, size),
rank: make([]int, size),
}
for i := 0; i < size; i++ {
uf.parent[i] = i
}
return uf
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) {
rootX := uf.Find(x)
rootY := uf.Find(y)
if rootX != rootY {
if uf.rank[rootX] < uf.rank[rootY] {
uf.parent[rootX] = rootY
} else if uf.rank[rootX] > uf.rank[rootY] {
uf.parent[rootY] = rootX
} else {
uf.parent[rootY] = rootX
uf.rank[rootX]++
}
}
}
func isSimilar(a, b string) bool {
diff := 0
for i := 0; i < len(a); i++ {
if a[i] != b[i] {
diff++
}
}
return diff == 0 || diff == 2
}
func numSimilarGroups(strs []string) int {
n := len(strs)
uf := NewUnionFind(n)
count := n
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if isSimilar(strs[i], strs[j]) && uf.Find(i) != uf.Find(j) {
count--
uf.Union(i, j)
}
}
}
return count
}Algorithm
Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n.
Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи.
Верните количество оставшихся групп.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.