C ++中的相似字符串组

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个字符串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

          回到顶部