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

假设我们有两个长度相同且只有小写字母的字符串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

• res：= res + my_map [P [i]]与2不同

• res：= res + 1 +（（（[[[i]与P [n-i-1]]相同时为1，否则为0））

• res：= res + 2

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

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

• my_map [Q [i]]：= 1

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

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

• my_map：=新映射

• my_map [P [i]]：= 1

• 如果P [i]与P [n-i-1]相同，则

• 如果Q [i]在my_map中，则

• 除此以外，

• 如果Q [n-i-1]在my_map中，则

• 除此以外，

• 大小：= my_map的大小

• 如果大小等于4，则

• 否则，当大小等于3时，则

• 否则，当大小等于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