0839. Similar String Groups

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(),最后看并查集中有几个集合即可。

代码 #


package leetcode

import (
	"github.com/halfrost/LeetCode-Go/template"
)

func numSimilarGroups(A []string) int {
	uf := template.UnionFind{}
	uf.Init(len(A))
	for i := 0; i < len(A); i++ {
		for j := i + 1; j < len(A); j++ {
			if isSimilar(A[i], A[j]) {
				uf.Union(i, j)
			}
		}
	}
	return uf.TotalCount()
}

func isSimilar(a, b string) bool {
	var n int
	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			n++
			if n > 2 {
				return false
			}
		}
	}
	return true
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者