<div>
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:
<pre>Input: strs = ["tars","rats","arts","star"] Output: 2 </pre>
Example 2:
<pre>Input: strs = ["omv","ovm"] Output: 1 </pre>
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.
</div>
题目大意：
单词列表中，可以分成多少组，每组里面的单词互相之间至少有一对可以通过交换一个位置变成另一个单词
解题思路：
典型求连通集个数，类似于Num of island，用BFS。难点在于怎么找到neighbor，用遍历每一个单词的方式
解题步骤：
N/A
注意事项：
- 难点在于怎么找到neighbor，用遍历每一个单词的方式，判断是否buddyStrings Leetcode 0859
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31def numSimilarGroups(self, strs: List[str]) -> int:
if not strs:
return 0
visited, groups, word_set = set(), 0, set(strs)
for s in strs:
if s in visited:
continue
self.bfs(word_set, s, visited)
groups += 1
return groups
def bfs(self, word_set, start, visited):
queue = collections.deque([start])
visited.add(start)
while queue:
node = queue.popleft()
for s in word_set:
if s in visited:
continue
if node == s or not self.buddyStrings(node, s):
continue
queue.append(s)
visited.add(s)
def buddyStrings(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
if s == goal and len(set(s)) < len(goal): # any dups
return True
diff = [(a, b) for a, b in zip(s, goal) if a != b]
return True if len(diff) == 2 and diff[0] == diff[1][::-1] else False
算法分析：
时间复杂度为O(nL)，空间复杂度O(n)
