Kiểm tra xem một chuỗi có hoán vị thành chuỗi đối xứng hay không trong Python

Giả sử chúng ta có một chuỗi s. Chúng ta cần kiểm tra xem có hoán vị (anagram) nào của chuỗi đó tạo thành chuỗi đối xứng (palindrome) hay không.

Ví dụ, nếu đầu vào là s = "aarcrec", thì đầu ra sẽ là True vì một hoán vị của chuỗi này là "racecar" - một chuỗi đối xứng.

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

• freq := một từ điển lưu trữ tần suất xuất hiện của từng ký tự.
• odd_count := 0 (đếm số ký tự xuất hiện lẻ lần).
• Duyệt qua các giá trị tần suất trong freq:
  • Nếu tần suất là số lẻ, tăng odd_count lên 1.
• Nếu odd_count > 1, trả về False (không thể tạo chuỗi đối xứng).
• Ngược lại, trả về True.

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

Ví dụ

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

Đầu vào

"aarcrec"

Đầu ra

True