Python程序:计算最小交换次数以使字符串变成回文字符串
假设我们有一个字符串s,我们必须找到使其成为回文字符串所需的最小相邻交换次数。如果没有这种解决方案,则返回-1。
因此,如果输入是s =“xxyy”,则输出将为2,因为我们可以交换中间的“x”和“y”所以字符串为“xyxy”,然后交换前两个“x”和“y”以获得“yxxy”,这是回文的。
要解决这个问题,我们将遵循以下步骤−
- 定义一个名为util()的函数。它将采用s
-
seen:=一个新的map
-
对于s中的每个i,执行以下操作
- seen[i]:= 1+(已经存在,则为0,否则为seen[i])
- odd_count:=0
-
对于seen的每个键值对,请执行以下操作
- 如果value是奇数,则
- odd_count:= odd_count+1
- 如果odd_count与2相同,则
- 返回False
- 如果value是奇数,则
- 返回True
-
从main方法中执行以下操作−
-
swaps:=0
-
如果util(s)为真,则
- left:=0
-
right:= s的大小-1
-
s:=通过从s中取字符而获得的新字符列表
-
当left<right时,执行以下操作
- 如果s[left]不同于s[right],则
-
k:= right
-
当k > left and s[k]与s[left]不同,时执行以下操作
- k:=k-1
- 如果k与left相同,则
- swaps:=swaps+1
-
s[left],s[left+1]:=s[left+1],s[left]
-
否则,
- 当k < right时,执行以下操作
-
交换s[k],s[k + 1]
-
k:=k+1
-
swaps:=swaps+1
-
left:=left + 1
-
right:=right − 1
-
否则,
-
left:= left+1
-
right:= right-1
-
返回swaps
- return -1
Python示例
让我们看下面的实现以获得更好的理解−
class Solution:
def solve(self, s):
def util(s):
seen = {}
for i in s:
seen[i] = seen.get(i, 0) + 1
odd_count = 0
for k, val in seen.items():
if val & 1 == 1:
odd_count += 1
if odd_count == 2:
return False
return True
swaps = 0
if util(s):
left = 0
right = len(s) - 1
s = list(s)
while left < right:
if s[left] != s[right]:
k = right
while k > left and s[k] != s[left]:
k -= 1
if k == left:
swaps += 1
s[left], s[left + 1] = s[left + 1], s[left]
else:
while k < right:
s[k], s[k + 1] = s[k + 1], s[k]
k += 1
swaps += 1
left += 1
right -= 1
else:
left += 1
right -= 1
return swaps
return -1
ob = Solution()
s = "xxyy"
print(ob.solve(s))
输入
"xxyy"
输出
2