ตรวจสอบว่าสตริงสามารถเรียงใหม่เป็น palindrome พิเศษได้หรือไม่ใน Python

สมมติว่าเรามีสตริง เราต้องตรวจสอบว่าตัวอักษรของสตริงที่กำหนดสามารถสลับตำแหน่งเพื่อสร้าง palindrome ได้หรือไม่

เช่น ถ้าอินพุตเป็น s = "aarcrce" ผลลัพธ์จะเป็น True เนื่องจากเราสามารถสลับตัวอักษรได้เป็น "racecar" ซึ่งเป็น palindrome

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:

• size := 256
• freq := อาร์เรย์ขนาด 256 เติมด้วย 0
• สำหรับ i ในช่วง 0 ถึงขนาดของ s ทำ
  • เพิ่มความถี่ของตัวอักษร s[i] ใน freq ขึ้น 1
• odd_count := 0
• สำหรับ i ในช่วง 0 ถึง size ทำ
  • ถ้า freq[i] เป็นคี่ แล้ว
    • odd_count := odd_count + 1
  • ถ้า odd_count > 1 แล้ว
    • คืนค่า False
• คืนค่า True

ลองดูการนำไปใช้ดังต่อไปนี้เพื่อเข้าใจได้ดียิ่งขึ้น:

ตัวอย่าง

size = 256
def solve(s):
    freq = [0] * size
    for i in range(0, len(s)):
        freq[ord(s[i])] = freq[ord(s[i])] + 1
    odd_count = 0
    for i in range(0, size):
        if freq[i] % 2 == 1:
            odd_count = odd_count + 1
        if odd_count > 1:
            return False
    return True

s = "aarcrce"
print(solve(s))

อินพุต

"aarcrce"

ผลลัพธ์

True