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