#839
Similar String Groups
expert · 1275 · lc hard +32 · verified · 56.1% accepted · 2,461 likes · top 50%
Description
Two strings X and Y are similar if they are identical, or if exactly one swap of two characters at distinct positions within X makes it equal to Y.
For example, "tars" and "rats" are similar (swap positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to any of them.
Those three form one similarity group {"tars", "rats", "arts"}, and {"star"} forms another. A word belongs to a group if it is similar to at least one other word in that group.
Given a list strs where every word is an anagram of every other word, return the number of similarity groups.
Example 1:
Input: strs = ["tars","rats","arts","star"]
Output: 2
Example 2:
Input: strs = ["omv","ovm"]
Output: 1
Code
1
2
3