848. Similar Word Groups
A librarian sorts shelf labels. Every string in words has the same length, and all of them are anagrams of one another. Two labels are called similar if they are identical, or if exchanging two letters at two different positions of one label turns it into the other. Similarity is passed along chains: if A is similar to B and B is similar to C, then A, B and C belong to the same group even when A and C are not similar to each other.
Return the number of groups. Labels may repeat in the list; each entry counts as a member of a group, and identical entries always lie in the same group.
Example 1
- Input:
- words = ["stop","tsop","post","pots"]
- Output:
- 2
- Explanation:
stop and tsop differ by swapping the first two letters, post and pots by swapping the last two; every cross pair differs in four positions, so there are two groups.
Example 2
- Input:
- words = ["mno","mno","nmo","omn"]
- Output:
- 1
- Explanation:
The duplicate
mnocounts as similar to itself,nmois one swap frommno, andomnis one swap fromnmo(first and last letters), so all four form one group.
Example 3
- Input:
- words = ["abcd","badc","cdab"]
- Output:
- 3
- Explanation:
Each pair of words differs in four positions, so no two are similar and there are three groups.
Constraints
- 1 ≤ words.length ≤ 3 * 104
- 1 ≤ words[i].length ≤ 8
- words consist of lowercase letters and all words are anagrams of each other
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n * L^3)
- Space
- O(n * L)