Pythonで2つの文字列を等しくするために必要な前処理移動の最小数を見つけます

同じ長さで小文字のみの2つの文字列PとQがあるとすると、以下の操作を適用した後、文字列Pを文字列Qと等しくするために必要な、文字列Pの前処理移動の最小数をカウントする必要があります-

• 任意のインデックスiを選択し、文字piとqiを入れ替えます。

• 任意のインデックスiを選択し、文字piとpn – i –1を入れ替えます。

• 任意のインデックスiを選択し、文字qiとqn – i –1を入れ替えます。

注 −範囲内のiの値（0≤i

1回の移動で、Pの文字を他の英語のアルファベットの文字に変更できます。

したがって、入力がP =“ pqprpqp”、Q =“ qprpqpp”の場合、出力は、P0 ='q'、P2 ='r'、P3 ='p'、P4='と設定した場合と同様に4になります。 q'とPは「qqrpqqp」になります。その後、次の一連の操作によって等しい文字列を取得できます：swap（P1、Q1）およびswap（P1、P5）。

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

• n：=Pのサイズ

• res：=0

• 0からn/2の範囲のiの場合、実行

  • my_map：=新しいマップ

  • my_map [P [i]]：=1

  • P[i]がP[n--i --1]と同じ場合、

    • my_map [P [n --i --1]]：=my_map [P [n --i --1]] + 1

  • Q [i]がmy_mapにある場合、

    • my_map [Q [i]]：=my_map [Q [i]] + 1

  • それ以外の場合

    • my_map [Q [i]]：=1

  • Q [n --i --1]がmy_mapにある場合、

    • my_map [Q [n --1 --i]]：=my_map [Q [n --1 --i]] + 1

  • それ以外の場合

    • my_map [Q [n --1 --i]]：=1

  • size：=my_mapのサイズ

  • サイズが4と同じ場合、

    • res：=res + 2

  • それ以外の場合、サイズが3と同じ場合、

    • res：=res + 1 +（（P[i]がP[n --i --1]と同じ場合は1）、それ以外の場合は0）

  • それ以外の場合、サイズが2と同じ場合、

    • res：=res + my_map[P[i]]は2と同じではありません

• n mod 2が1と同じで、P [n/2]がQ[n/ 2]と同じでない場合、

  • res：=res + 1

• 解像度を返す

例

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

def count_preprocess(P, Q):
   n = len(P)
   res = 0
   for i in range(n // 2):
      my_map = dict()
      my_map[P[i]] = 1
      if P[i] == P[n - i - 1]:
         my_map[P[n - i - 1]] += 1
      if Q[i] in my_map:
         my_map[Q[i]] += 1
      else:
         my_map[Q[i]] = 1
      if Q[n - i - 1] in my_map:
         my_map[Q[n - 1 - i]] += 1
      else:
         my_map[Q[n - 1 - i]] = 1
      size = len(my_map)
      if (size == 4):
         res += 2
      elif (size == 3):
         res += 1 + (P[i] == P[n - i - 1])
      elif (size == 2):
         res += my_map[P[i]] != 2
   if (n % 2 == 1 and P[n // 2] != Q[n // 2]):
      res += 1
   return res

A = "pqprpqp"
B = "qprpqpp"
print(count_preprocess(A, B))

入力

"pqprpqp", "qprpqpp"

出力

4