在 C++ 中查找 K 相似字符串的 K 值的程序

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

假设我们有两个字符串 s 和 t。当我们可以将 s 中两个字母的位置恰好交换 K 次以便结果字符串是 t 时，这两个字符串是 K 相似的。我们有两个字谜 s 和 t，我们必须找到最小的 K，其中 s 和 t 是 K 相似的。

因此，如果输入类似于 s = "abc", t = "bac"，那么输出将为 1。

示例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int kSimilarity(string A, string B) {
      if (A == B)
         return 0;
      unordered_set<string> visited;
      visited.insert(A);
      queue<string> q;
      q.push(A);
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            string curr = q.front();
            q.pop();
            int i = 0;
            while (i < curr.size() && curr[i] == B[i])
               i++;
            for (int j = i + 1; j < curr.size(); j++) {
               if (curr[i] == curr[j])
                  continue;
               if (curr[j] != B[i])
                  continue;
               if (curr[j] == B[j])
                  continue;
               swapp(curr, i, j);
               if (curr == B)
                  return lvl;
               if (!visited.count(curr)) {
                  visited.insert(curr);
                  q.push(curr);
               }
               swapp(curr, i, j);
            }
         }
      }
      return -1;
   }
   void swapp(string &s, int i, int j) {
      char x = s[i];
      char y = s[j];
      s[i] = y;
      s[j] = x;
   }
};
main(){
   Solution ob;
   cout << (ob.kSimilarity("abc", "bac"));
}

输入

"abc", "bac"

1

以上是 在 C++ 中查找 K 相似字符串的 K 值的程序 的全部内容， 来源链接： utcz.com/z/345738.html