K-C++の類似した文字列

2つの文字列AとBがあるとします。これらの2つの文字列は、Aの2つの文字の位置を正確にK回入れ替えて、結果の文字列がBになる場合、Kに似ています（Kは1つの非負の整数）。 2つのアナグラムAとB、AとBがKに類似している最小のKを見つける必要があります。

したがって、入力がA ="abc"、B ="bac"の場合、出力は2になります。

これを解決するには、次の手順に従います-

• 関数swapp（）を定義します。これには、文字列s、i、j、

  が必要です。

• x：=s [i]、y：=s [j]

• s [i]：=y、s [j]：=x

• メインの方法から、次のようにします-

• AがBと同じ場合、：、0を返します

• 訪問した1セットを定義する

• 訪問済みにAを挿入

• 1つのキューqを定義し、Aをqに挿入します

• 初期化レベル：=1の場合、qが空でない場合は、更新（レベルを1増やします）、実行-

  • sz：=qのサイズ

  • szがゼロ以外の場合、反復ごとにszを1ずつ減らし、-

    を実行します。

    • curr：=qの最初の要素

    • qから要素を削除

    • i：=0

    • （i

      • （iを1増やします）

    • 初期化j：=i + 1の場合、j

      • curr[i]がcurr[j]と同じである場合、-

        • 次の部分を無視し、次の反復にスキップします

      • curr[j]がB[i]と等しくない場合、-

        • 次の部分を無視し、次の反復にスキップします

      • curr[j]がB[j]と同じ場合、-

        • 次の部分を無視し、次の反復にスキップします

      • swapp（curr、i、j）

      • currがBと同じ場合、-

        • レベルを返す

      • 訪問したカウント（curr）を呼び出さない場合は、-

        • 訪問先にcurrを挿入

        • qにcurrを挿入

      • swapp（curr、i、j）

• -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