Chương trình đếm số lần hoán đổi tối thiểu cần thiết để biến nó thành palindrome bằng Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số lần hoán đổi liền kề tối thiểu cần thiết để biến nó thành một palindrome. Nếu không có cách nào như vậy để giải quyết, hãy trả về -1.

Vì vậy, nếu đầu vào là s =​​"xxyy", thì đầu ra sẽ là 2, vì chúng ta có thể hoán đổi giữa "x" và "y" để chuỗi là "xyxy" và sau đó hoán đổi hai đầu tiên "x" và " y "để lấy" yxxy "và đây là palindrome.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm dùng (). Điều này sẽ mất s

• đã thấy:=một bản đồ mới

• đối với mỗi tôi trong s, hãy làm

  • đã thấy [i]:=1 + (đã xem [i] nếu tồn tại, nếu không thì 0)

• Od_count:=0

• đối với mỗi cặp giá trị chính được xem, thực hiện

  • nếu giá trị là số lẻ thì

    • Od_count:=retail_count + 1

  • nếu số_lượng lẻ bằng 2 thì

    • trả về Sai

• trả về True

• Từ phương thức chính, hãy làm như sau -

• hoán đổi:=0

• nếu sử dụng là đúng, thì

  • trái:=0

  • right:=size of s - 1

  • s:=một danh sách các ký tự mới bằng cách lấy từ s

  • trong khi trái

    • nếu s [left] không giống s [right] thì

      • k:=đúng

      • trong khi k> left và s [k] không giống với s [left], thực hiện

        • k:=k - 1

      • nếu k giống với bên trái thì

        • swaps:=swaps + 1

        • s [left], s [left + 1]:=s [left + 1], s [left]

      • nếu không,

        • trong khi k

          • hoán đổi s [k], s [k + 1]

          • k:=k + 1

          • swaps:=swaps + 1

        • left:=left + 1

        • right:=right - 1

    • nếu không,

      • left:=left + 1

      • right:=right - 1

  • trả lại hoán đổi

• trả về -1

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"xxyy"

Đầu ra

2