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

以上是 C ++中按字典分类的最小等效字符串 的全部内容, 来源链接: utcz.com/z/354964.html

回到顶部