Kiểm tra chuỗi đối xứng bằng Python (palindrome)
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
Trong bài này · 12
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ó:
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:
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í 0Câ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.
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 TrueVò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 " ,.!?-":
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 FalseLà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 // 2phé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
Trong khung bẫy "trả
Truengay khi thấy một cặp giống nhau", lời gọila_doi_xung("2012")trả về ____ (TruehayFalse).Trong khung bẫy NFD, vì sao
tu == tu[::-1]choFalsedù"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
- Vì
Trong ví dụ làm sạch, những câu nào cho
Truesau khi qualam_sach?"Ô tô""""Ổ cắm, mắc ô""12 3 21"
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ố.
import unicodedata
def so_cho_sua(s):
pass # Viết thân hàm thay cho dòng nàyCâ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ủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
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.