Kiểm tra xem chuỗi có thể sắp xếp lại thành palindrome đặc biệt hay không trong Python

Giả sử chúng ta có một chuỗi, cần kiểm tra xem các ký tự của chuỗi có thể xáo trộn để tạo thành palindrome hay không.

Ví dụ, s = "aarcrce", đầu ra True vì có thể xáo trộn thành "racecar" - một palindrome.

Các bước giải quyết:

• size := 256 (mã ASCII mở rộng).
• freq := mảng 256 phần tử khởi tạo 0.
• Duyệt i từ 0 đến độ dài s-1: tăng freq[ord(s[i])] lên 1.
• odd_count := 0.
• Duyệt i từ 0 đến 255:
  • Nếu freq[i] là lẻ, odd_count += 1.
  • Nếu odd_count > 1, trả về False.
• Trả về True.

Xem ví dụ dưới đây để hiểu rõ hơn:

Ví dụ

size = 256

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

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

Đầu vào

"aarcrce"

Đầu ra

True