Bỏ qua đến nội dung chính
Mục lục

Kiểm tra chuỗi đối xứng bằng Python (palindrome)

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 1/10 · Chương 25

Bài tập phỏng vấn Python

  • 8 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Kiểm tra chuỗi đối xứng (palindrome) bằng Python là hỏi một chuỗi đọc xuôi và đọc ngược có giống nhau không, như "12321" hay "Ổ cắm, mắc ổ!". Đây là câu khởi động quen thuộc của các buổi phỏng vấn: trang này đi qua hai cách giải và cách làm sạch câu, cái giá của từng cách, rồi cho bạn một bài tập được chấm ngay trên trang.

Cần biết trước: đảo chuỗi, duyệt chuỗi theo chỉ số và chuẩn hóa Unicode.

Đề bài

Lớp của Minh làm một trò chơi chữ: ai tìm được câu tiếng Việt đọc ngược vẫn y nguyên thì được cộng điểm. Viết hàm la_doi_xung(s) trả về True khi s là chuỗi đối xứng, False khi không phải.

Ví dụ vào ra: "12321" cho True, "Đà Lạt" cho False.

Trước khi viết code, hãy hỏi lại những điều đề chưa nói:

  • Chữ hoa và chữ thường có tính là giống nhau không? Ở trò chơi này: có.

  • Dấu cách và dấu câu có được bỏ qua không? Có, bỏ dấu cách và các dấu , . ! ? -.

  • Chữ có dấu có được coi như chữ không dấu không? Không: "ô" khác "o".

  • Chuỗi rỗng thì sao? Là chuỗi đối xứng, vì đọc ngược vẫn là chuỗi rỗng.

Cách 1: so chuỗi với bản đảo của nó

Lát cắt s[::-1] cho một chuỗi mới, đọc từ ký tự cuối về ký tự đầu. Chuỗi đối xứng khi nó bằng bản đảo của chính nó:

python
def la_doi_xung(s):
    return s == s[::-1]

print(la_doi_xung("12321"))
print(la_doi_xung("Đà Lạt"))
print(la_doi_xung("Ô tô"))
print("Ô tô"[::-1])

KẾT QUẢ

True
False
False
ôt Ô

Một dòng là đủ cho hai ví dụ đầu. Dòng thứ ba cho thấy hàm còn thiếu phần làm sạch: bản đảo của "Ô tô" là "ôt Ô", khác chữ hoa và lệch chỗ dấu cách. Phần làm sạch nằm ở mục cuối, vì nó dùng được cho cả hai cách.

Vì sao cách đảo chuỗi tốn công hơn cần thiết

Người phỏng vấn thường hỏi tiếp: bản đảo tốn gì? Hàm dưới đây đếm thử với một mã dài 1.000 ký tự mà ký tự đầu đã khác ký tự cuối:

python
def vi_tri_lech_dau(s):
    ban_dao = s[::-1]
    for i in range(len(s)):
        if s[i] != ban_dao[i]:
            return i
    return -1

ma = "b" + "a" * 999
print(len(ma[::-1]), "ký tự chép sang bản đảo")
print("cặp lệch đầu tiên ở vị trí", vi_tri_lech_dau(ma))

KẾT QUẢ

1000 ký tự chép sang bản đảo
cặp lệch đầu tiên ở vị trí 0

Câu trả lời đã có ngay ở vị trí 0, nhưng cách 1 vẫn chép đủ 1.000 ký tự sang một chuỗi mới, tức tốn thêm bộ nhớ bằng cả chuỗi. Khi chuỗi đúng là đối xứng, phép so == đi hết n vị trí, trong khi mỗi cặp đầu, cuối thật ra chỉ cần so một lần: một nửa số phép so là thừa.

Cách 2: hai chỉ số đi từ hai đầu vào giữa

Thay cho bản đảo, bạn so ký tự đầu với ký tự cuối, ký tự thứ hai với ký tự áp cuối, và cứ thế vào giữa. Ký tự đối xứng với s[i] là s[-1 - i]: khi i là 0 thì -1 - i là -1, ký tự cuối.

python
def la_doi_xung(s):
    for i in range(len(s) // 2):
        if s[i] != s[-1 - i]:
            return False
    return True

print(la_doi_xung("12321"), la_doi_xung("2002"))
print(la_doi_xung("Đà Lạt"), la_doi_xung(""))

KẾT QUẢ

True True
False True

Vòng lặp chỉ chạy len(s) // 2 lượt: với độ dài lẻ, ký tự chính giữa không cần so với ai, còn chuỗi rỗng cho range(0) nên hàm trả True ngay. Gặp cặp lệch đầu tiên là return False, nên mã "b" + "a" * 999 ở mục trên chỉ tốn một phép so. Hàm không tạo chuỗi mới nào. Hai chỉ số chạy về phía nhau là một dạng của kỹ thuật hai con trỏ.

Trên CPython, cách 1 thường chạy nhanh hơn cách 2 nhiều lần dù phải chép chuỗi, vì cả phép đảo lẫn phép so đều chạy bằng C. Cách 2 thắng ở chỗ khác: không tốn bộ nhớ thêm và dừng sớm. Nói được cả hai điều này với người phỏng vấn là một điểm cộng.

Bỏ qua hoa thường, dấu cách và dấu câu

Câu thật có chữ hoa, dấu cách và dấu câu. Hàm lam_sach chuẩn hóa chuỗi về dạng NFC, viết thường bằng lower() của bài phương thức chuỗi, rồi dựng chuỗi mới chỉ giữ các ký tự không nằm trong " ,.!?-":

python
import unicodedata

def lam_sach(s):
    s = unicodedata.normalize("NFC", s).lower()
    sach = ""
    for ky_tu in s:
        if ky_tu not in " ,.!?-":
            sach += ky_tu
    return sach

for cau in ["Ô tô", "Ổ cắm, mắc ổ!", "Đà Lạt"]:
    sach = lam_sach(cau)
    print(f"{cau:<14} {sach:<10} {sach == sach[::-1]}")

KẾT QUẢ

Ô tô           ôtô        True
Ổ cắm, mắc ổ!  ổcắmmắcổ   True
Đà Lạt         đàlạt      False

Làm sạch xong thì cách nào cũng dùng được, ở đây là cách 1 cho gọn. Chữ có dấu vẫn giữ dấu, nên "ô" và "o" vẫn khác nhau, đúng như đề đã chốt. Đổi "Ô tô" thành "Ô to" rồi chạy lại: dòng đầu in False.

Nói gì với người phỏng vấn

Đầu tiên là các câu hỏi làm rõ của mục Đề bài: hoa thường, dấu cách, dấu câu, chữ có dấu, chuỗi rỗng. Rồi bạn trình bày theo thứ tự:

  • "Cách viết gọn là so chuỗi với s[::-1]. Nó tốn thêm bộ nhớ bằng cả chuỗi và luôn chép hết, kể cả khi ký tự đầu đã lệch."

  • "Tôi so từ hai đầu vào giữa, tối đa n // 2 phép so, dừng ngay ở cặp lệch đầu tiên, không tạo chuỗi mới. Số bước tăng cùng nhịp với độ dài chuỗi, cách viết Big O gọi là O(n)."

  • "Trước khi so, tôi chuẩn hóa NFC, viết thường và bỏ dấu cách, dấu câu, vì chữ tiếng Việt có thể đến ở dạng NFD."

  • "Tôi đã xét chuỗi rỗng, chuỗi một ký tự, độ dài chẵn và lẻ."

Kiểm tra nhanh

  1. Trong khung bẫy "trả True ngay khi thấy một cặp giống nhau", lời gọi la_doi_xung("2012") trả về ____ (True hay False).

  2. Trong khung bẫy NFD, vì sao tu == tu[::-1] cho False dù "mộccộm" đọc ngược vẫn y nguyên?

    • Vì [::-1] làm mất dấu của chữ có dấu
    • Vì dấu là ký tự riêng, đảo chuỗi đặt dấu lên trước chữ cái của nó
    • Vì chuỗi NFD dài hơn nên Python không so được
  3. Trong ví dụ làm sạch, những câu nào cho True sau khi qua lam_sach?

    • "Ô tô"
    • ""
    • "Ổ cắm, mắc ô"
    • "12 3 21"
Đúng hết lần đầu +15 XP

Bài tập

Đếm số ký tự phải sửa để câu đối xứng

Trò chơi chữ có thêm luật: câu chưa đối xứng thì được sửa, mỗi lần sửa đổi một ký tự thành ký tự khác, và ai sửa ít lần nhất thì thắng. Viết hàm so_cho_sua(s) trả về số ký tự ít nhất phải đổi để phần còn lại của s sau khi làm sạch là chuỗi đối xứng. Làm sạch như mục bỏ dấu câu: chuẩn hóa NFC bằng unicodedata.normalize(), viết thường, bỏ dấu cách và các dấu , . ! ? -. Chữ có dấu khác chữ không dấu.

Ví dụ: so_cho_sua("Mộc cộn") trả về 1: sau khi làm sạch là "mộccộn", chỉ cặp m, n lệch.

Trả về: số ký tự phải đổi, một int.

Ôn lại: duyệt chuỗi theo chỉ số.

python
import unicodedata

def so_cho_sua(s):
    pass  # Viết thân hàm thay cho dòng này

Câu hỏi thường gặp

Từ palindrome nghĩa là gì?

Palindrome là từ tiếng Anh cho chuỗi đọc xuôi hay đọc ngược đều như nhau, tiếng Việt gọi là chuỗi đối xứng hay câu đọc xuôi ngược. Trong lập trình, nó thường là bài khởi động ở buổi phỏng vấn, vì vừa đủ ngắn để viết trong vài phút vừa có nhiều trường hợp biên.

Kiểm tra số đối xứng như 12321 trong Python có khác chuỗi không?

Không khác: đổi số sang chuỗi bằng str() rồi dùng đúng hàm của trang, la_doi_xung(str(12321)) cho True. Số âm như -121 thì không đối xứng, vì bản đảo của "-121" là "121-". Đổi kiểu bằng str() nằm ở bài ép kiểu.

Có nên dùng reversed() để kiểm tra chuỗi đối xứng không?

Được nhưng không gọn hơn: reversed(s) cho từng ký tự từ cuối về đầu, phải gom lại thành chuỗi hay list rồi mới so, nên vẫn tốn bộ nhớ như cách 1. Ba cách đảo [::-1], reverse(), reversed() được so sánh ở bài đảo ngược list.

Chủ đề

kiểm tra chuỗi đối xứng python

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập