LeetCode力扣839.相似字符串组

题目描述

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

给你多个字符串。每个字符串都是其他所有字符串的一个字母异位词。请问给出的字符串中有多少个相似字符串组？

输入输出样例

输入 #1

4
tars
rats
arts
star

输出 #1

2

解释：
"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；
"rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

提示：
1 <= 字符串个数 <= 300
1 <= 每个字符串长度 <= 300
每个字符串只包含小写字母。
所有字符串都具有相同的长度，且是彼此的字母异位词。

解题思路

解决本题需对并查集做一定了解。将两字符串之间的相似关系抽象为有向图中两地的连通关系。将有相似关系的字符串串连在同一棵树上，最后求字符串组的个数实际上就是求树的个数，也就是根节点的个数。

解决方案

用 string 类型的数组存储字符串，用数组下标表示字符串的编号，若两字符串相似，就让他们的编号认爸爸，用 parent 数组表示爸爸和儿子的关系，如 parent[3]=2 就表示编号为3的字符串认编号为2的字符串当爸爸。这样会形成多对父子关系，如果某次判断的两个字符串已经在其他父子关系中出现过，那就认爸爸的爸爸的爸爸......当爸爸，也就是认根结点当爸爸，如此类推。最后只需要找有多少给根结点即可。细节看代码。

代码

此代码不支持上机检测

#include<iostream>
#include<string>

using namespace std;

int n;	//字符串个数 
string str[305];	//存储n个字符串 
int parent[305];	//认爸爸 
int rank[305];	//方便判断认谁当爸爸能使树的深度最小 
int vis[305];	//标记根节点 
int cnt;	//记录根节点个数 

int init(int a[],int x)	//数组初始化 
{
	for(int i=0;i<n;i++)
		a[i]=x;
}

bool is_similar(string a,string b)
{
	int len=a.length(); 
	int ans=0;
	for(int i=0;i<len;i++)	//遍历字符串 
	{
		if(a[i]!=b[i]) ans++;	//若两字符串对应位置不相同ans+1 
		if(ans>2) return false;	//超过两个位置不同则不相似返回false 
	}
	return true;
}

int find_root(int x)	//找数组下标为x的结点的根节点数组下标 
{
	int x_root=x;
	while(parent[x_root]!=-1) x_root=parent[x_root];	//等于-1说明一直是初值，没有被改变，那么它没有父节点，一定是根结点 
	return x_root;
}

int union_str(int x,int y)	//合并下标为x和y的两结点所在的树，也就是两棵树的根结点认爸爸 
{
	int x_root=find_root(x);
	int y_root=find_root(y);
	if(x_root==y_root)	//若x和y根结点相同说明本就在同一棵树，不需要合并 
	{
		return 0;
	}
	else	//不在同一棵树就要开始让爸爸了 
	{
		if(rank[x_root]>rank[y_root])	//接下来同过rank值来确定谁认谁当爸爸，其实无所谓谁当谁爸爸，只是为了使树的深度小一点，执行find_root函数时可以少执行几次 
		{
			parent[y_root]=x_root;	//y的根结点认x的根结点当爸爸 
			vis[y_root]=0;	//认x的根结点当爸爸以后y以前的根节点就不是根节点了，vis赋0 
		}
		else if(rank[x_root]<rank[y_root])
		{
			parent[x_root]=y_root;	//x的根结点认y的根结点当爸爸 
			vis[x_root]=0;	//认y的根结点当爸爸以后y以前的根节点就不是根节点了，vis赋0  
		}
		else
		{
			parent[x_root]=y_root;	//x的根结点认y的根结点当爸爸
			rank[y_root]++;
			vis[x_root]=0;	//认y的根结点当爸爸以后y以前的根节点就不是根节点了，vis赋0
		}
		return 1;
	}
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>str[i];
	init(parent,-1);
	init(vis,1);
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n;j++)	//对没两个字符串之间进行遍历比较 
		{
			if(is_similar(str[i],str[j]))	//如果相似 
				union_str(i,j);	//合并，或者说认爸爸 
		}
	}
	for(int i=0;i<n;i++)	//统计最终树的个数，也就是根结点的个数 
		cnt+=vis[i];
	cout<<cnt;
	return 0;
}