mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 01:15:57 +08:00
60 lines
3.3 KiB
Markdown
Executable File
60 lines
3.3 KiB
Markdown
Executable File
# [839. Similar String Groups](https://leetcode.com/problems/similar-string-groups/)
|
||
|
||
|
||
## 题目
|
||
|
||
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:**
|
||
|
||
1. `A.length <= 2000`
|
||
2. `A[i].length <= 1000`
|
||
3. `A.length * A[i].length <= 20000`
|
||
4. All words in `A` consist of lowercase letters only.
|
||
5. All words in `A` have the same length and are anagrams of each other.
|
||
6. The judging time limit has been increased for this question.
|
||
|
||
|
||
## 题目大意
|
||
|
||
如果我们交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。
|
||
|
||
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
|
||
|
||
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。我们给出了一个不包含重复的字符串列表 A。列表中的每个字符串都是 A 中其它所有字符串的一个字母异位词。请问 A 中有多少个相似字符串组？
|
||
|
||
|
||
提示：
|
||
|
||
- A.length <= 2000
|
||
- A[i].length <= 1000
|
||
- A.length * A[i].length <= 20000
|
||
- A 中的所有单词都只包含小写字母。
|
||
- A 中的所有单词都具有相同的长度，且是彼此的字母异位词。
|
||
- 此问题的判断限制时间已经延长。
|
||
|
||
|
||
备注：
|
||
|
||
- 字母异位词[anagram]，一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
|
||
|
||
|
||
|
||
|
||
## 解题思路
|
||
|
||
|
||
- 给出一个字符串数组，要求找出这个数组中，"不相似"的字符串有多少种。相似的字符串的定义是：如果 A 和 B 字符串只需要交换一次字母的位置就能变成两个相等的字符串，那么 A 和 B 是相似的。
|
||
- 这一题的解题思路是用并查集。先将题目中的“相似”的定义转换一下，A 和 B 相似的意思是，A 和 B 中只有 2 个字符不相等，其他字符都相等，这样交换一次才能完全相等。有没有可能这两个字符交换了也不相等呢？这种情况不用考虑，因为题目中提到了给的字符串都是 `anagram` 的(`anagram` 的意思是，字符串的任意排列组合)。那么这题就比较简单了，只需要判断每两个字符串是否“相似”，如果相似就 `union()`，最后看并查集中有几个集合即可。
|