PythonでKに類似した文字列のKの最小値を見つけるプログラム

2つの文字列sとtがあるとします。これらの2つの文字列は、s内の2つの文字の位置を正確にK回入れ替えて、結果の文字列がtになる場合、Kに似ています。したがって、2つのアナグラムsとtがあり、sとtがKに類似している最小のKを見つける必要があります。

したがって、入力がs ="abc" t ="bac"の場合、出力は1になります。

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

• 関数neighbors（）を定義します。これにはnew_dataが必要です

• new_dataの各インデックスiと値cについて、実行します

  • cがt[i]と同じでない場合、

    • ループから出てきます

• i + 1からnew_data-1のサイズまでの範囲のjの場合、実行

  • u[j]がt[i]と同じ場合、

    • new_data [i] new_data [j]

      を交換します

    • new_dataのすべての要素を結合して文字列を生成し、次の呼び出しからこの領域から再開する

      を返します。

    • new_data [i] new_data [j]

      を交換します

• mainメソッドから、次の手順を実行します。

• q：=1つのキューを作成してペアを挿入（s、0）

• 見た：=sからの新しいセット

• qが空でない間、実行します

  • （u、swap_cnt）：=qの最初のアイテムで、qから削除します

  • uがtと同じ場合、

    • swap_cntを返す

  • ネイバーのvごとに（リストとしてu）、実行します

    • vが表示されていない場合は、

      • 見たとおりにvをマーク

      • qの最後に（v、swap_cnt + 1）を挿入します

• 0を返す

例

理解を深めるために、次の実装を見てみましょう

from collections import deque
def solve(s, t):
   def swap(data, i, j):
      data[i], data[j] = data[j], data[i]

   def neighbors(new_data):
      for i, c in enumerate(new_data):
         if c != t[i]: break

      for j in range(i+1, len(new_data)):
         if u[j] == t[i]:
            swap(new_data, i, j)
            yield "".join(new_data)
            swap(new_data, i, j)

   q = deque([(s, 0)])
   seen = set(s)
   while q:
      u, swap_cnt = q.popleft()
      if u == t:
         return swap_cnt
      for v in neighbors(list(u)):
         if v not in seen:
            seen.add(v)
            q.append((v, swap_cnt+1))
   return 0

s = "abc"
t = "bac"
print(solve(s, t))

入力

"abc, bac"

出力

1