Python程序:计算最小交换次数以使字符串变成回文字符串

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
  • 返回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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程