在 Python 中查詢使兩個字串相等所需的最小預處理移動次數

假設我們有兩個相同長度的字串 P 和 Q，它們只包含小寫字母，我們需要計算在應用以下操作後使字串 P 等於字串 Q 所需的字串 P 的最小預處理移動次數：

  • 選擇任何索引 i 並交換字元 pi 和 qi。

  • 選擇任何索引 i 並交換字元 pi 和 pn – i – 1。

  • 選擇任何索引 i 並交換字元 qi 和 qn – i – 1。

注意 - i 的值在範圍 (0 ≤ i < n) 內

在一個移動中，我們可以將 P 中的一個字元更改為英語字母表中的任何其他字元。

因此，如果輸入類似於 P = “pqprpqp”，Q = “qprpqpp”，則輸出將為 4，因為如果我們將 P0 設定為 'q'，P2 設定為 'r'，P3 設定為 'p' 以及 P4 設定為 'q'，則 P 將為“qqrpqqp”。之後，我們可以透過以下操作序列獲得相等的字串：交換(P1, Q1) 和交換(P1, P5)。

為了解決這個問題，我們將遵循以下步驟：

  • n := P 的大小

  • res := 0

  • 對於 i 的範圍從 0 到 n / 2，執行以下操作：

    • 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 的大小

    • 如果 size 與 4 相同，則

      • res := res + 2

    • 否則，當 size 與 3 相同，則

      • res := res + 1 + (當 (P[i] 與 P[n - i - 1] 相同) 時為 1，否則為 0)

    • 否則，當 size 與 2 相同，則

      • res := res + my_map[P[i]] 不與 2 相同

  • 如果 n mod 2 與 1 相同，並且 P[n / 2] 不與 Q[n / 2] 相同，則

    • res := res + 1

  • 返回 res

示例

讓我們看看以下實現以更好地理解：

即時演示

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

更新於： 2020 年 8 月 20 日

199 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告