Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

假设我们有两个字符串s和t。当我们可以精确交换s中两个字母的位置K次，使得结果字符串为t时，这两个字符串是K相似的。我们有两个异位词s和t，我们必须找到最小的K，使得s和t是K相似的。

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

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

  • 定义一个函数swapp()，它将接收字符串s、i、j作为参数，

  • x := s[i]，y := s[j]

  • s[i] := y，s[j] := x

  • 从主方法执行以下操作：

  • 如果A与B相同，则：返回0

  • 定义一个集合visited

  • 将A插入到visited中

  • 定义一个队列q，将A插入到q中

  • 从lvl := 1开始初始化，当q不为空时，更新（将lvl增加1），执行以下操作：

    • sz := q的大小

    • 当sz不为零时，每次迭代减少sz，执行以下操作

      • curr := q的第一个元素

      • 从q中删除元素

      • i := 0

      • 当(i < curr的大小且curr[i]与B[i]相同)时，执行以下操作

        • (将i增加1)

      • 从j := i + 1开始初始化，当j < curr的大小，更新（将j增加1），执行以下操作

        • 如果curr[i]与curr[j]相同，则

          • 忽略以下部分，跳到下一次迭代

        • 如果curr[j]不等于B[i]，则

          • 忽略以下部分，跳到下一次迭代

        • 如果curr[j]与B[j]相同，则

          • 忽略以下部分，跳到下一次迭代

        • swapp(curr, i, j)

        • 如果curr与B相同，则

          • 返回lvl

        • 如果未调用visited的count(curr)，则

          • 将curr插入到visited中

          • 将curr插入到q中

        • swapp(curr, i, j)

  • 返回-1

示例

让我们看看以下实现，以便更好地理解

Open Compiler
#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"

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

1

更新于： 2021年10月7日

207 次查看

开启你的职业生涯

通过完成课程获得认证

立即开始
广告