Description
Two strings X and Y are similar if we can swap two letters of X to get Y. A group of strings is similar if each string is similar to some other string in the group. Given a list of strings strs, return the number of groups.
Examples
strs = ["tars","rats","arts","star"]2Two groups: {tars,rats,arts} and {star}.
strs = ["abc","bca","cab","xyz"]2Two groups: {abc,bca,cab} and {xyz}. The first three strings can all be made similar through swaps: abc→bca (swap positions 0,1), abc→cab (swap positions 0,2), bca→cab (swap positions 0,1). The string xyz cannot be made similar to any of the others since it has completely different characters.
strs = ["abcd","abdc","acdb","bacd","efgh"]3Three groups: {abcd,abdc}, {acdb,bacd}, and {efgh}. First group: abcd→abdc by swapping positions 2,3. Second group: acdb→bacd by swapping positions 0,1. The string efgh forms its own group as it shares no characters with the others and cannot be made similar through any swaps.
Constraints
- •
1 ≤ strs.length ≤ 300 - •
1 ≤ strs[i].length ≤ 300