在 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 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告