在 Python 中查找使两个字符串相等所需的最少预处理移动次数

pythonserver side programmingprogramming更新于 2025/9/30 15:08:17

假设我们有两个长度相同且仅包含小写字母的字符串 P 和 Q,我们必须计算在应用以下操作后使字符串 P 等于字符串 Q 所需的最少预处理移动次数 −

  • 选择任意索引 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”。之后我们可以通过以下操作序列获得相等的字符串:swap(P1, Q1) 和 swap(P1, P5)。

为了解决这个问题,我们将遵循以下步骤 −

  • n := P 的大小

  • res := 0

  • 对于范围为 0 到 n / 2 的 i,执行

    • my_map := a new 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

  • 返回 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

相关文章


有用资源