Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
839. Similar String Groups.go
839. Similar String Groups_test.go
README.md

README.md

839. 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(),最后看并查集中有几个集合即可。
You can’t perform that action at this time.