程序计算在Python中使其回文所需的最小交换次数

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个字符串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