โปรแกรมนับจำนวนสวอปขั้นต่ำที่จำเป็นในการทำให้เป็นพาลินโดรมใน Python

สมมติว่าเรามีสตริง s เราต้องหาจำนวนสวอปที่อยู่ติดกันขั้นต่ำที่จำเป็นในการทำให้มันเป็นพาลินโดรม หากไม่มีวิธีแก้ปัญหา ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น s ="xxyy" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถสลับระหว่าง "x" และ "y" ตรงกลางได้ ดังนั้นสตริงจึงเป็น "xyxy" จากนั้นจึงสลับ "x" สองตัวแรกกับ "x" y" เพื่อให้ได้ "yxxy" และนี่คือ palindrome

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา s

• เห็นแล้ว :=แผนที่ใหม่

• สำหรับแต่ละ i ทำ

  • เห็น[i] :=1 + (เห็น[i] ถ้ามีอยู่ 0)

• odd_count :=0

• สำหรับแต่ละคู่ของค่าคีย์ที่เห็น ให้ทำ

  • ถ้าค่าเป็นเลขคี่แล้ว

    • odd_count :=odd_count + 1

  • ถ้า odd_count เหมือนกับ 2 แล้ว

    • คืนค่าเท็จ

• คืนค่า True

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• สวอป :=0

• ถ้า util(s) เป็นจริง แล้ว

  • ซ้าย :=0

  • ขวา :=ขนาด s - 1

  • s :=รายการตัวละครใหม่โดยนำมาจาก s

  • ขณะที่ซ้าย <ขวา ทำ

    • ถ้า s[left] ไม่เหมือนกับ s[right] แล้ว

      • k :=ถูกต้อง

      • ในขณะที่ k> left และ s[k] ไม่เหมือนกับ s[left] ให้ทำ

        • k :=k - 1

      • ถ้า k เท่ากับ left แล้ว

        • สวอป :=สวอป + 1

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

      • มิฉะนั้น

        • ในขณะที่ k <ถูกต้อง ทำ

          • สลับ s[k], s[k + 1]

          • k :=k + 1

          • สวอป :=สวอป + 1

        • ซ้าย :=ซ้าย + 1

        • ขวา :=ขวา - 1

    • มิฉะนั้น

      • ซ้าย :=ซ้าย + 1

      • ขวา :=ขวา - 1

  • คืนสวอป

• กลับ -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