在 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,执行
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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

