查找在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时，则
如果nmod2与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