LeetCode - 839. Similar String Groups | Ryan's Blog

LeetCode - 839. Similar String Groups | Ryan's Blog

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

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 A of strings.  Every string in A is an anagram of every other string in A.  How many groups are there?

Example 1

Input: ["tars","rats","arts","star"]  Output: 2  

Note:

• A.length <= 2000
• A[i].length <= 1000
• A.length * A[i].length <= 20000
• All words in A consist of lowercase letters only.
• All words in A have the same length and are anagrams of each other.

Solution

This problem is very similar to the Union-Find problem. When we want to know if a string X belongs to a specific classY, we need to iterate through all the elements in the classY and see if any of them is similar to X. If so, we know X and the elements in classY should be in the same class. As in the Union-Find algorithm, we have a root representing a class. Let Y denote the root of classY. We now have two choice: (1) assign the classY to X or (2) let X represent a new classX and assign classX to Y. It seems that the second approach is more convenient.

Read full article from LeetCode - 839. Similar String Groups | Ryan's Blog