Chuyển tới nội dung chính

Bài toán chuỗi thường gặp

Bạn sẽ học được gì

Ba dạng bài chuỗi xuất hiện liên tục trong bài tập và phỏng vấn: palindrome (đối xứng), anagram (đảo chữ), và đếm ký tự. Quan trọng hơn cả lời giải là mẫu đằng sau: hai con trỏ và bảng đếm.

1. Palindrome: chuỗi đọc xuôi ngược như nhau​

"radar", "abba", "12321" là palindrome. Mẫu giải: hai con trỏ từ hai đầu tiến vào giữa, so từng cặp. Lệch một cặp là không phải palindrome.

🐞 Kiểm tra "abba" có là palindrome?Bước 1/6
1def la_palindrome(s):
2  trai, phai = 0, len(s) - 1
3  while trai < phai:
4      if s[trai] != s[phai]:
5          return False
6      trai += 1
7      phai -= 1
8  return True
Biến tại bước này
sabba
trai0
phai3
👉 Hai con trỏ ở hai đầu.

2. Anagram: hai chuỗi cùng tập ký tự, khác thứ tự​

"listen" và "silent" là anagram. Mẫu giải kinh điển: đếm ký tự — nếu hai chuỗi có cùng số lượng mỗi ký tự thì là anagram. (Cách khác: sắp xếp cả hai rồi so, nhưng O(n log n) chậm hơn.)

Đang tải trình chạy code…

Dùng dict làm bảng đếm → duyệt mỗi chuỗi một lần → O(n), nhanh hơn cách sắp xếp.

3. Đếm ký tự / tần suất​

Rất nhiều bài quy về "đếm mỗi thứ xuất hiện bao nhiêu lần" bằng dict:

Đang tải trình chạy code…

4. Hai mẫu chìa khoá​

MẫuKhi nào dùngĐộ phức tạp
Hai con trỏso sánh/đối xứng từ hai đầu (palindrome, đảo)O(n) thời gian, O(1) bộ nhớ
Bảng đếm (dict)so sánh thành phần, tần suất (anagram, đếm)O(n) thời gian, O(k) bộ nhớ

Hai mẫu này (cùng sliding window) sẽ học kỹ ở Trụ 4 — Mẫu giải bài. Ở đây bạn gặp chúng lần đầu qua bài chuỗi.

5. Mẫu nhận diện​

  • "Đối xứng", "đọc xuôi ngược", "từ hai đầu" → hai con trỏ.
  • "Cùng tập ký tự", "tần suất", "đếm xuất hiện" → dict đếm.
  • Đừng vội sắp xếp (O(n log n)) nếu đếm bằng dict (O(n)) là đủ.

6. 🎮 Trò chơi: Bài toán chuỗi​

🎮 Bài toán chuỗiCâu 1/4· Điểm 0· 🔥 0

Nhận diện mẫu: đối xứng → hai con trỏ; tần suất/anagram → dict đếm.

Cặp nào là anagram của nhau?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Kỹ thuật hai con trỏ kiểm tra palindrome có độ phức tạp bộ nhớ?
2. Cách nhanh nhất kiểm tra anagram thường là?
3. Cấu trúc nào lý tưởng để đếm tần suất ký tự?

8. Hoàn thành — XONG Chương 2.1! 🎉​

…

☑️ Hết Chương 2.1 (Mảng & chuỗi). Tiếp theo: 2.2.1 — Danh sách liên kết đơn.