KのKの値を見つけるプログラム-C++の類似した文字列

2つの文字列sとtがあるとします。これらの2つの文字列は、s内の2つの文字の位置を正確にK回入れ替えて、結果の文字列がtになる場合、Kに似ています。 2つのアナグラムsとtがあり、sとtがKに類似している最小の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を返します

• 訪問した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と同じ場合、次のようになります。

        • レベルを返す

      • 訪問者のcount（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