LeetCode force buckle 839 Similar string group

Title Description

If two letters at different positions in the string X are exchanged to make it equal to the string Y, then the two strings X and Y are said to be similar. If the two strings themselves are equal, they are similar.

Give you multiple strings. Each string is an alphabetic ectopic of all other strings. How many similar string groups are there in the given string?

Sample input and output

Input \1

4
tars
rats
arts
star

Output \1

2

Explanation:
"tars" and "rats" are similar (swap the positions of 0 and 2);
"Rats" and "arts" are also similar, but "star" is not similar to "s tars", "rats", or "arts".
They form two association groups through similarity: {"tars", "rats", "arts"} and {"star"}. Note that "tars" and "arts" are in the same group, even if they are not similar. Formally, for each group, to determine a word in the group, it only needs to be similar to at least one word in the group.

Tips:
1 < = number of strings < = 300
1 < = length of each string < = 300
Each string contains only lowercase letters.
All strings have the same length and are alphabetic ectonyms of each other.

Problem solving ideas

To solve this problem, we need to have a certain understanding of parallel search set. The similar relation between two strings is abstracted as the connected relation between two places in a directed graph. String strings with similar relationships in a tree. Finally, the number of string groups is actually the number of trees, that is, the number of root nodes.

Solution

String arrays are used to store strings. Array subscripts are used to represent the number of strings. If two strings are similar, their numbers will be used to identify the father. Parent arrays are used to represent the relationship between father and son. For example, parent[3]=2 means that the string with number 3 identifies the string with number 2 as the father. In this way, multiple pairs of parent-child relationships will be formed. If the two strings of a certain judgment have already appeared in other parent-child relationships, then recognize the father of the father's father's father To be a father is to recognize the root node as a father, and so on. Finally, you only need to find the number of root nodes. See the code for details.

code

This code does not support online detection

#include<iostream>
#include<string>

using namespace std;

int n;	//Number of strings 
string str[305];	//Store n strings 
int parent[305];	//Recognize Dad 
int rank[305];	//It's easy to judge who can be the father to minimize the depth of the tree 
int vis[305];	//Mark root node 
int cnt;	//Record the number of root nodes 

int init(int a[],int x)	//Array initialization 
{
	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++)	//Traversal string 
	{
		if(a[i]!=b[i]) ans++;	//If the corresponding positions of two strings are different, ans+1 
		if(ans>2) return false;	//If more than two positions are different, they are not similar. false is returned 
	}
	return true;
}

int find_root(int x)	//Find the root node array subscript of the node whose array subscript is x 
{
	int x_root=x;
	while(parent[x_root]!=-1) x_root=parent[x_root];	//If it is equal to -1, it means that it is always the initial value and has not been changed. Then it has no parent node and must be the root node 
	return x_root;
}

int union_str(int x,int y)	//Merge the trees of two nodes with subscripts x and y, that is, the root nodes of the two trees 
{
	int x_root=find_root(x);
	int y_root=find_root(y);
	if(x_root==y_root)	//If the root nodes of x and y are the same, it means that they are in the same tree and do not need to be merged 
	{
		return 0;
	}
	else	//Not in the same tree. It's about to let Dad 
	{
		if(rank[x_root]>rank[y_root])	//Next, the rank value is used to determine who knows who is the father. In fact, it doesn't matter who is the father. It's just to make the depth of the tree smaller and execute find_ The root function can be executed several times less 
		{
			parent[y_root]=x_root;	//The root of y recognizes the root of x as its father 
			vis[y_root]=0;	//After the root node of x is recognized as the father, the root node before y is not the root node, and vis is assigned 0 
		}
		else if(rank[x_root]<rank[y_root])
		{
			parent[x_root]=y_root;	//The root of x recognizes the root of y as its father 
			vis[x_root]=0;	//After the root node of Y is recognized as the father, the root node before y is not the root node, and vis is assigned 0  
		}
		else
		{
			parent[x_root]=y_root;	//The root of x recognizes the root of y as its father
			rank[y_root]++;
			vis[x_root]=0;	//After the root node of Y is recognized as the father, the root node before y is not the root node, and vis is assigned 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++)	//Traversal comparison between two strings 
		{
			if(is_similar(str[i],str[j]))	//If similar 
				union_str(i,j);	//Merger, or father recognition 
		}
	}
	for(int i=0;i<n;i++)	//Count the number of final trees, that is, the number of root nodes 
		cnt+=vis[i];
	cout<<cnt;
	return 0;
}