Algorithm
Problem Name: 839. Similar String Groups
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.
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".
Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.
We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?
Example 1:
Input: strs = ["tars","rats","arts","star"] Output: 2
Example 2:
Input: strs = ["omv","ovm"] Output: 1
Constraints:
1 <= strs.length <= 3001 <= strs[i].length <= 300strs[i]consists of lowercase letters only.- All words in
strshave the same length and are anagrams of each other.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const numSimilarGroups = function (A) {
const all = new Set(A)
const isSimilar = function (w1, w2) {
if (w1 === w2) return true
let misMatch = 0
for (let i = 0; i < w1.length; i++) {
if (w1[i] !== w2[i]) misMatch++
if (misMatch > 2) return false
}
return true
}
const recur = function (s) {
all.delete(s)
for (let n of all) {
if (isSimilar(s, n)) {
recur(n)
}
}
}
let ans = 0
while (all.size) {
const current = all.values().next().value
recur(current)
ans++
}
return ans
}
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSimilarGroups(self, A):
def explore(s):
visited.add(s)
for v in edges[s]:
if v not in visited: explore(v)
res, edges, visited = 0, {}, set()
if len(A) >= 2 * len(A[0]):
strs = set(A)
for s in A:
if s not in edges: edges[s] = set()
for i in range(len(s) - 1):
for j in range(i + 1, len(s)):
new = s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
if new in strs:
edges[s].add(new)
if new in edges: edges[new].add(s)
else: edges[new] = {s}
else:
for s in A:
if s not in edges: edges[s] = set()
for t in A:
if s != t:
same = 0
for i, c in enumerate(t):
if c == s[i]: same += 1
if same == len(s) - 2:
edges[s].add(t)
if t in edges: edges[t].add(s)
else: edges[t] = {s}
for s in A:
if s not in visited:
res += 1
explore(s)
return res
Input
Output