Pythonで特定のアナグラムを作成するために必要な最小限のスワップを見つけるプログラム

2つの文字列SとTがあり、それらが互いにアナグラムであるとします。 Tと同じにするために、Sで必要なスワップの最小数を見つける必要があります。

したがって、入力がS ="kolkata" T ="katloka"の場合、出力は3になり、このシーケンスでスワップできます[katloka（指定）、kotlaka、koltaka、kolkata]。

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

• 関数util（）を定義します。これにはS、T、iが必要です
• i> =Sのサイズの場合、
  • 0を返す
• S[i]がT[i]と同じ場合、
  • return util（S、T、i + 1）
• x：=T [i]
• ret：=99999
• i + 1からTのサイズまでの範囲のjについては、
  • xがS[j]と同じ場合、
    • S[i]とS[j]を入れ替える
    • ret：=最小のretおよび（1 + util（S、T、i + 1））
    • S[i]とS[j]を入れ替える
• return ret
• メインの方法から次の手順を実行します。
• return util（S、T、0）

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

例

class Solution:
   def util(self, S, T, i) :
      S = list(S)
      T = list(T)
      if i >= len(S):
         return 0
      if S[i] == T[i]:
         return self.util(S, T, i + 1)
      x = T[i]
      ret = 99999;
      for j in range(i + 1, len(T)):
         if x == S[j]:
            S[i], S[j] = S[j], S[i]
            ret = min(ret, 1 + self.util(S, T, i + 1))
            S[i], S[j] = S[j], S[i]
      return ret
     
   def solve(self, S, T):
      return self.util(S, T, 0)

ob = Solution()
S = "kolkata"
T = "katloka"
print(ob.solve(S, T))

入力

"kolkata", "katloka"

出力

3