程序计算在Python中使其回文所需的最小交换次数
假设我们有一个字符串s,我们必须找到使其成为回文式所需的最小相邻交换数。如果没有这种解决方法,则返回-1。
因此,如果输入类似于s =“ xxyy”,则输出将为2,因为我们可以交换中间的“ x”和“ y”,使字符串为“ xyxy”,然后交换前两个“ x”和“ y”得到“ yxxy”,这就是回文。
Example(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
以上是 程序计算在Python中使其回文所需的最小交换次数 的全部内容, 来源链接: utcz.com/z/357975.html