C ++中按字典分类的最小等效字符串
假设我们具有相同长度的字符串A和B，现在我们可以说A[i]和B[i]是等效字符。因此，例如，如果A=“abc”和B=“cde”，则我们有'a'='c'，'b'='d'和'c'='e'。等效字符遵循任何等效关系的通常规则：
自反性：“a”=“a”
对称性：“a”=“b”表示“b”=“a”
及物性：'a'='b'和'b'='c'表示'a'='c'
现在，例如，考虑到上面A和B的等效信息，S=“eed”，“acd”和“aab”是等效字符串，而“aab”是S在字典上最小的等效字符串。在这里，我们必须找到通过使用来自A和B的等价信息，获得S的词典上最小的等效字符串。以词典的顺序返回可以这种方式形成的所有单词。
因此，如果输入类似于A=“parker”，B=“morris”和S=“parser”，则输出将为“makkek”。这是因为基于A和B中的等效信息，我们可以将它们的字符分组为[m，p]，[a，o]，[k，r，s]，[e，i]。因此，每个组中的字符是等价的，并按字典顺序排序。因此答案是“makkek”。
为了解决这个问题，我们将遵循以下步骤-
创建一个名为parent的数组
定义一个名为的方法getParent()，它将使用字符x
如果parent[x–ASCII'a']为-1，则返回x-ASCII'a'
parent[x–'a'的ASCII]：=getParent（'a'的ASCII+parent[x–'a'的ASCII]）
返回parent[x–'a'的ASCII]
创建另一个方法，称为union()a和b
parentA：=getParent(a)和parent：=getParent(b)
因此，如果parentA=父级，则在parentA<父级时返回，否则返回parent[parentB]：=parentA，否则返回parent[parentA]：=parent
从主要方法中，执行以下操作-
设置parent：=大小为26的数组，并使用-1填充它
当我在0到25的范围内
执行联合（A[i]，B[i]）
创建一个空白字符串ret
对于0到S大小的i
ret：=ret+getParent（S[i]）+'a'
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <int> parent;
int getParent(char x){
//cout << x << "-- " << x-'a' << endl;
if(parent[x - 'a'] == -1) return x - 'a';
return parent[x - 'a'] = getParent('a' + parent[x - 'a']);
}
void unionn(char a, char b){
int parentA = getParent(a);
int parentB = getParent(b);
if(parentA == parentB) return;
if(parentA < parentB){
parent[parentB] = parentA;
}else{
parent[parentA] = parentB;
}
}
string smallestEquivalentString(string A, string B, string S) {
parent = vector <int>(26, -1);
for(int i = 0; i < A.size(); i++){
unionn(A[i], B[i]);
}
string ret = "";
for(int i = 0; i < S.size(); i++){
ret += getParent(S[i]) + 'a';
}
return ret;
}
};
main(){
Solution ob;
cout <<
(ob.smallestEquivalentString("parker","morris","parser"));
}输入项
"parker" "morris" "parser"
输出结果
makkek