查找在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