ตรวจสอบว่าแอนนาซแกรมของสตริงเป็นพาลินโดรมได้หรือไม่ใน Python

ภาพรวม

บทความนี้อธิบายวิธีตรวจสอบว่าสตริงที่กำหนดสามารถจัดเรียงตัวอักษรใหม่ (anagram) ให้กลายเป็นพาลินโดรม (palindrome) ได้หรือไม่

เงื่อนไขสำคัญ

สตริงสามารถจัดเป็นพาลินโดรมได้ ก็ต่อเมื่อ ตัวอักษรที่มีความถี่คี่ (odd frequency) มีได้มากสุด 1 ตัวเท่านั้น (สำหรับสตริงความยาวคี่) หรือไม่มีเลย (สำหรับสตริงความยาวคู่)

อัลกอริทึม

1. นับความถี่ของแต่ละตัวอักษร
2. นับจำนวนตัวอักษรที่มีความถี่เป็นคี่
3. ถ้าจำนวนตัวอักษรที่มีความถี่คี่ > 1 คืนค่า False, มิฉะนั้นคืนค่า True

ตัวอย่างโค้ด Python

from collections import defaultdict

def solve(s):
    freq = defaultdict(int)
    for char in s:
        freq[char] += 1
    odd_count = 0
    for f in freq.values():
        if f % 2 == 1:
            odd_count += 1
    if odd_count > 1:
        return False
    return True

s = "aarcrec"
print(solve(s))  # True (racecar)

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

ตัวอย่าง "aarcrec" สามารถจัดเป็น "racecar" ซึ่งเป็นพาลินโดรม วิธีนี้มีประสิทธิภาพ O(n) โดย n คือความยาวสตริง เหมาะสำหรับการตรวจสอบรูปแบบข้อความ