C ++中的相似字符串组

假设我们有两个字符串X和Y,如果可以交换X的两个字母,它们是相似的,因此等于Y。另外,如果两个字符串X和Y相等,则它们相似。例如,考虑两个字符串,例如“ tars”和“ rats”相似,如果我们交换t和r,则可以找到另一个,现在“ rats”和“ arts”相似,但是“ star”不同类似于“焦油”,“鼠”或“艺术品”。现在我们可以看到,它们通过相似性形成了两个相连的组:{“ tars”,“ rats”,“ arts”}和{“ star”}。尽管“焦油”和“艺术品”不相似,但它们属于同一组。因此,当且仅当单词与该组中的至少一个其他单词相似时,每个组才使得该单词在该组中。假设我们有一个字符串列表A。A中的每个字符串都是A中其他所有字符串的相似词。我们必须找出那里有多少个组?

因此,如果输入类似于[“ tars”,“ rats”,“ arts”,“ star”],则输出将为2

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个父数组

  • 定义数组等级

  • 定义一个函数getParent(),这将需要x,

    • 返回x

    • 如果parent [x]与-1相同,则-

    • 返回parent [x] = getParent(parent [x])

    • 定义一个函数unionn(),它将取x,y,

      • 等级[parY]:=等级[parY] +等级[parX]

      • parent [parX]:= parY

      • 等级[parX]:=等级[parX] +等级[parY]

      • parent [parY]:= parX

      • 返回假

      • parX:= getParent(x),parY:= getParent(y)

      • 如果parX与parY相同,则-

      • 如果rank [parX]> = rank [parY],则-

      • 除此以外

      • 返回真

      • 定义一个函数ok(),它将取s1,s2,

        • 如果s1 [i]不等于s2 [i],则-

        • 如果cnt> 2,则-

        • (将cnt增加1)

        • 返回假

        • cnt:= 0

        • 对于初始化i:= 0,当i <s1的大小时,更新(将i增加1),执行-

        • 返回真

        • 从主要方法中,执行以下操作-

        • ret:= 0

        • n:= A的大小

        • ret:= n

        • parent:=一个大小为n的数组,并用-1填充

        • rank:=大小为n的数组,并用1填充

        • 对于初始化i:= 0,当i <n时,更新(将i增加1),执行-

          • 如果ok(A [i],A [j])不为零,则-

          • (将retret减少1)

          • 如果unionn(i,j)不为零,则-

          • 对于初始化j:= i + 1,当j <n时,更新(将j增加1),-

          • 返回ret

          让我们看下面的实现以更好地理解-

          示例

          #include <bits/stdc++.h>

          using namespace std;

          void print_vector(vector<auto> v){

             cout << "[";

             for(int i = 0; i<v.size(); i++){

                cout << v[i] << ", ";

             }

             cout << "]"<<endl;

          }

          class Solution {

             public:

             vector<int> parent;

             vector<int> rank;

             int getParent(int x){

                if (parent[x] == -1)

                return x;

                return parent[x] = getParent(parent[x]);

             }

             bool unionn(int x, int y){

                int parX = getParent(x);

                int parY = getParent(y);

                if (parX == parY)

                return false;

                if (rank[parX] >= rank[parY]) {

                   rank[parX] += rank[parY];

                   parent[parY] = parX;

                } else {

                   rank[parY] += rank[parX];

                   parent[parX] = parY;

                }

                return true;

             }

             bool ok(string& s1, string& s2){

                int cnt = 0;

                for (int i = 0; i < s1.size(); i++) {

                   if (s1[i] != s2[i])

                   cnt++;

                   if (cnt > 2)

                   return false;

                }

                return true;

             }

             int numSimilarGroups(vector<string>& A){

                int ret = 0;

                int n = A.size();

                ret = n;

                parent = vector<int>(n, -1);

                rank = vector<int>(n, 1);

                for (int i = 0; i < n; i++) {

                   for (int j = i + 1; j < n; j++) {

                      if (ok(A[i], A[j])) {

                         if (unionn(i, j))

                         ret--;

                      }

                   }

                }

                return ret;

             }

          };

          main(){

             Solution ob;

             vector<string> v = {"tars","rats","arts","star"};

             cout << (ob.numSimilarGroups(v));

          }

          输入值

          {"tars","rats","arts","star"}

          输出结果

          2

          以上是 C ++中的相似字符串组 的全部内容, 来源链接: utcz.com/z/352561.html

          回到顶部