Similar String Groups — LeetCode 839 Python Solution
HardDepth-First SearchBreadth-First SearchUnion FindArrayHash TableString
- Problem
- #839
- Pattern
- Union-Find
- Reading time
- 6 min
- Source
- leetcode.com
The problem
Two strings, X and Y, are considered similar if either they are identical or we can make them equivalent by swapping at most two letters (in distinct positions) within the string X. For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".
Example
- Input
- strs = ["tars","rats","arts","star"]
- Output
- 2
Python solution
Python
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def numSimilarGroups(self, strs: List[str]) -> int:
n, m = len(strs), len(strs[0])
uf = UnionFind(n)
for i, s in enumerate(strs):
for j, t in enumerate(strs[:i]):
if sum(s[k] != t[k] for k in range(m)) <= 2 and uf.union(i, j):
n -= 1
return nComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 839. Similar String Groups is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 839. Similar String Groups?
- LeetCode 839. Similar String Groups is rated Hard on LeetCode.
- What is the time complexity of LeetCode 839. Similar String Groups?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 839. Similar String Groups?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 839. Similar String Groups cover?
- LeetCode 839. Similar String Groups is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table and String on LeetCode.