Bài học

Duyệt và biến đổi xâu kí tự

Mục tiêu bài học

Sau bài này, em duyệt và biến đổi được một xâu kí tự bằng cách gom kết quả vào một list, rồi gọi ''.join(...) đúng một lần — thay vì nối chuỗi bằng s = s + c trong vòng lặp — và giải thích được bằng lập luận vì sao cách làm này nhanh hơn hẳn khi xâu dài.

Sau bài này, em duyệt và biến đổi được một xâu kí tự bằng cách gom kết quả vào một `list`, rồi gọi `''.join(...)` đúng một lần — thay vì nối chuỗi bằng `s = s + c` trong vòng lặp — và giải thích được bằng lập luận vì sao cách làm này nhanh hơn hẳn khi xâu dài.

Cần nhớ trước

Em cần nắm vững: kiểu dữ liệu str, vòng lặp for, lấy kí tự theo chỉ số s[i], hàm len(), và cách tạo list từ một xâu bằng list(s).

Em cần nắm vững: kiểu dữ liệu `str`, vòng lặp `for`, lấy kí tự theo chỉ số `s[i]`, hàm `len()`, và cách tạo `list` từ một xâu bằng `list(s)`.

Đề chuẩn Lớp 10 cho những bài duyệt xâu vài chục kí tự — cách viết nào cũng chạy tức thì, kể cả nối chuỗi từng bước bằng +. Đề HSG cho xâu dài tới hàng trăm nghìn, có khi hàng triệu kí tự, và giới hạn thời gian chạy chỉ một hai giây. Lúc đó, cách viết quen tay từ lớp dưới bắt đầu lộ vấn đề.

Đề chuẩn Lớp 10 cho những bài duyệt xâu vài chục kí tự — cách viết nào cũng chạy tức thì, kể cả nối chuỗi từng bước bằng `+`. Đề HSG cho xâu dài tới hàng trăm nghìn, có khi hàng triệu kí tự, và giới hạn thời gian chạy chỉ một hai giây. Lúc đó, cách viết quen tay từ lớp dưới bắt đầu lộ vấn đề.

Bài toán mở đầu — vì sao nối chuỗi quen thuộc lại chậm

Thử viết một hàm đảo ngược xâu bằng cách duyệt từ cuối về đầu, mỗi bước nối thêm một kí tự: ket_qua = ket_qua + s[i]. Với vài chục kí tự, chương trình chạy ngay. Nhưng tăng $n$ lên $10^6$ kí tự, chương trình bỗng "đứng hình" nhiều giây — dù mỗi bước trông chỉ là một phép cộng đơn giản, lặp $n$ lần.

Thử viết một hàm đảo ngược xâu bằng cách duyệt từ cuối về đầu, mỗi bước nối thêm một kí tự: `ket_qua = ket_qua + s[i]`. Với vài chục kí tự, chương trình chạy ngay. Nhưng tăng $n$ lên $10^6$ kí tự, chương trình bỗng "đứng hình" nhiều giây — dù mỗi bước trông chỉ là một phép cộng đơn giản, lặp $n$ lần.

Ý tưởng cốt lõi — xâu bất biến và cái giá của phép nối

Trong Python, xâu kí tự là bất biến (immutable): một khi đã tạo ra, nội dung của nó không bao giờ đổi tại chỗ. Lệnh ket_qua = ket_qua + s[i] trông như "thêm một kí tự vào cuối", nhưng Python phải cấp phát một vùng nhớ mới, sao chép toàn bộ ket_qua cũ vào đó, rồi mới thêm kí tự mới — theo đúng tính chất bất biến của kiểu str. Ở bước thứ $k$ , việc sao chép tốn khoảng $k$ đơn vị công; sau $n$ bước, tổng công sao chép là $1+2+\cdots+n=\dfrac{n(n+1)}{2}$ , tức bậc $O(n^2)$ .

Trong Python, xâu kí tự là **bất biến** (immutable): một khi đã tạo ra, nội dung của nó không bao giờ đổi tại chỗ. Lệnh `ket_qua = ket_qua + s[i]` trông như "thêm một kí tự vào cuối", nhưng Python phải cấp phát một vùng nhớ mới, sao chép toàn bộ `ket_qua` cũ vào đó, rồi mới thêm kí tự mới — theo đúng tính chất bất biến của kiểu `str`. Ở bước thứ $k$, việc sao chép tốn khoảng $k$ đơn vị công; sau $n$ bước, tổng công sao chép là $1+2+\cdots+n=\dfrac{n(n+1)}{2}$, tức bậc $O(n^2)$.

Mở rộng dành cho HSG

Kỹ thuật thay thế không nằm trong yêu cầu chuẩn tối thiểu của Lớp 10 (SGK chỉ dạy cách duyệt xâu, không phân tích độ phức tạp) — ta học thêm vì đây là kỹ thuật bắt buộc khi làm việc với dữ liệu lớn. Gom mọi kí tự cần thêm vào một list bằng append (chi phí trung bình $O(1)$ mỗi lần), rồi gọi ''.join(danh_sach) đúng một lần ở cuối. Tổng chi phí giảm còn $O(n)$ .

Kỹ thuật thay thế không nằm trong yêu cầu chuẩn tối thiểu của Lớp 10 (SGK chỉ dạy cách duyệt xâu, không phân tích độ phức tạp) — ta học thêm vì đây là kỹ thuật bắt buộc khi làm việc với dữ liệu lớn. Gom mọi kí tự cần thêm vào một `list` bằng `append` (chi phí trung bình $O(1)$ mỗi lần), rồi gọi `''.join(danh_sach)` đúng một lần ở cuối. Tổng chi phí giảm còn $O(n)$.

Số phép sao chép tăng theo

\dfrac{n(n+1)}{2}

nếu nối chuỗi từng bước, nhưng chỉ tăng theo

n

nếu gom vào list rồi join một lần.Số phép sao chép tăng theo $\dfrac{n(n+1)}{2}$ nếu nối chuỗi từng bước, nhưng chỉ tăng theo $n$ nếu gom vào list rồi join một lần.

Ví dụ 1 — Đảo ngược xâu không dùng slicing

Ví dụ

Ví dụ 1 — Đảo ngược xâu "TINHOC" không dùng slicing

1
Đề chuẩn chỉ cần viết s[::-1] — một dòng, không quan tâm cơ chế bên trong. Đề này cấm dùng slicing và yêu cầu giải thích độ phức tạp, buộc em tự cài đặt và chứng minh thuật toán chạy $O(n)$ .
Đề chuẩn chỉ cần viết `s[::-1]` — một dòng, không quan tâm cơ chế bên trong. Đề này cấm dùng slicing và yêu cầu giải thích độ phức tạp, buộc em tự cài đặt và chứng minh thuật toán chạy $O(n)$.
2
Chuyển xâu thành list kí tự — vì list có thể đổi chỗ phần tử tại chỗ, khác với str. Dùng hai con trỏ: i xuất phát từ đầu, j xuất phát từ cuối, đổi chỗ từng cặp rồi tiến dần vào giữa.
Chuyển xâu thành `list` kí tự — vì `list` có thể đổi chỗ phần tử tại chỗ, khác với `str`. Dùng hai con trỏ: `i` xuất phát từ đầu, `j` xuất phát từ cuối, đổi chỗ từng cặp rồi tiến dần vào giữa.

def dao_nguoc_xau(s):
    ki_tu = list(s)
    i, j = 0, len(ki_tu) - 1
    while i < j:
        ki_tu[i], ki_tu[j] = ki_tu[j], ki_tu[i]
        i += 1
        j -= 1
    return ''.join(ki_tu)

4
Đảo toàn bộ xâu mà không tạo xâu trung gian nào chỉ cần mỗi kí tự di chuyển đúng một lần — đổi chỗ tại chỗ trong list là cách duy nhất làm được điều đó, không sao chép lặp lại như phép +.
5
Bước 0 (ban đầu): T I N H O C. Bước 1 ( $i{=}0,j{=}5$ , đổi T và C): C I N H O T. Bước 2 ( $i{=}1,j{=}4$ , đổi I và O): C O N H I T. Bước 3 ( $i{=}2,j{=}3$ , đổi N và H): C O H N I T — lúc này $i{=}3$ không còn nhỏ hơn $j{=}2$ nên dừng. Kết quả COHNIT khớp với "TINHOC"[::-1].
Bước 0 (ban đầu): `T I N H O C`. Bước 1 ($i{=}0,j{=}5$, đổi T và C): `C I N H O T`. Bước 2 ($i{=}1,j{=}4$, đổi I và O): `C O N H I T`. Bước 3 ($i{=}2,j{=}3$, đổi N và H): `C O H N I T` — lúc này $i{=}3$ không còn nhỏ hơn $j{=}2$ nên dừng. Kết quả `COHNIT` khớp với `"TINHOC"[::-1]`.
6
Ta có mỗi vòng lặp while đổi chỗ đúng một cặp $(i,j)$ rồi tiến vào giữa, nên sau tối đa $\lfloor n/2\rfloor$ vòng lặp thì $i \ge j$ và toàn bộ $n$ kí tự đã được đổi chỗ đúng vị trí đối xứng. Suy ra thuật toán chạy đúng trong $O(n)$ thời gian, dùng thêm $O(n)$ bộ nhớ cho danh sách ki_tu. Vậy hàm dao_nguoc_xau trả về xâu đảo ngược đúng, không dùng slicing.
Ta có mỗi vòng lặp `while` đổi chỗ đúng một cặp $(i,j)$ rồi tiến vào giữa, nên sau tối đa $\lfloor n/2\rfloor$ vòng lặp thì $i \ge j$ và toàn bộ $n$ kí tự đã được đổi chỗ đúng vị trí đối xứng. Suy ra thuật toán chạy đúng trong $O(n)$ thời gian, dùng thêm $O(n)$ bộ nhớ cho danh sách `ki_tu`. Vậy hàm `dao_nguoc_xau` trả về xâu đảo ngược đúng, không dùng slicing.

Ví dụ 2 — Hạ chữ thường và loại khoảng trắng thừa

Ví dụ

Ví dụ 2 — Chuyển xâu về chữ thường, loại khoảng trắng thừa

1
Đề chuẩn chỉ cần gọi s.lower(). Đề này thêm yêu cầu loại bỏ khoảng trắng thừa (nhiều dấu cách liên tiếp) mà không được dùng hàm dựng sẵn cho việc đó — buộc em tự theo dõi trạng thái "kí tự trước có phải khoảng trắng không" khi duyệt.
2
Duyệt một lượt, giữ một biến cờ dang_trong_khoang_trang. Chỉ thêm một dấu cách vào kết quả khi gặp khoảng trắng ĐẦU TIÊN sau một kí tự thường; các dấu cách liên tiếp sau đó bị bỏ qua.
3
```
def chuan_hoa(s):
    ket_qua = []
    dang_trong_khoang_trang = True  # bo khoang trang o dau
    for ch in s:
        ch = ch.lower()
        if ch == ' ':
            if not dang_trong_khoang_trang:
                ket_qua.append(' ')
            dang_trong_khoang_trang = True
        else:
            ket_qua.append(ch)
            dang_trong_khoang_trang = False
    if ket_qua and ket_qua[-1] == ' ':
        ket_qua.pop()
    return ''.join(ket_qua)
```
```python def chuan_hoa(s): ket_qua = [] dang_trong_khoang_trang = True # bo khoang trang o dau for ch in s: ch = ch.lower() if ch == ' ': if not dang_trong_khoang_trang: ket_qua.append(' ') dang_trong_khoang_trang = True else: ket_qua.append(ch) dang_trong_khoang_trang = False if ket_qua and ket_qua[-1] == ' ': ket_qua.pop() return ''.join(ket_qua) ```
4
Mỗi kí tự chỉ cần biết trạng thái ngay trước nó (đang ở giữa một đoạn khoảng trắng hay không) để quyết định có giữ lại dấu cách này hay không — đúng khuôn mẫu "duyệt một lượt, giữ một biến trạng thái nhỏ", biến bài toán tưởng phức tạp thành $O(n)$ .
Mỗi kí tự chỉ cần biết trạng thái ngay trước nó (đang ở giữa một đoạn khoảng trắng hay không) để quyết định có giữ lại dấu cách này hay không — đúng khuôn mẫu "duyệt một lượt, giữ một biến trạng thái nhỏ", biến bài toán tưởng phức tạp thành $O(n)$.
5
Với "Tin Hoc 10": khi gặp cụm 2 dấu cách sau "Tin", dấu cách đầu được giữ, dấu thứ hai bị bỏ vì cờ đã bật; tương tự với cụm 3 dấu cách sau "Hoc". Kết quả: "tin hoc 10".
6
Ta có biến cờ đúng bằng "kí tự liền trước trong kết quả có phải khoảng trắng hay không", nên tại mỗi kí tự khoảng trắng của đề bài, chương trình chỉ ghi thêm một dấu cách khi kết quả hiện tại chưa kết thúc bằng dấu cách. Do đó mọi cụm khoảng trắng liên tiếp trong s được rút gọn còn đúng một dấu cách, và dấu cách ở đầu hoặc cuối bị loại hoàn toàn. Vậy chuan_hoa chạy $O(n)$ và trả về đúng xâu đã hạ chữ thường, hết khoảng trắng thừa.
Ta có biến cờ đúng bằng "kí tự liền trước trong kết quả có phải khoảng trắng hay không", nên tại mỗi kí tự khoảng trắng của đề bài, chương trình chỉ ghi thêm một dấu cách khi kết quả hiện tại chưa kết thúc bằng dấu cách. Do đó mọi cụm khoảng trắng liên tiếp trong `s` được rút gọn còn đúng một dấu cách, và dấu cách ở đầu hoặc cuối bị loại hoàn toàn. Vậy `chuan_hoa` chạy $O(n)$ và trả về đúng xâu đã hạ chữ thường, hết khoảng trắng thừa.

Ví dụ 3 — Viết hoa chữ cái đầu mỗi từ, không dùng title()

Ví dụ

Ví dụ 3 — Viết hoa chữ cái đầu mỗi từ mà không gọi title()

1
Python có sẵn str.title(), nhưng hàm này coi CẢ chữ số là ranh giới từ: "lop10a".title() trả về "Lop10A" — viết hoa cả chữ a đứng sau số 10, điều thường KHÔNG phải ý muốn khi xử lý mã lớp học. Đề yêu cầu tự cài đặt đúng theo ranh giới là khoảng trắng, để tránh đúng cái bẫy này.
Python có sẵn `str.title()`, nhưng hàm này coi CẢ chữ số là ranh giới từ: `"lop10a".title()` trả về `"Lop10A"` — viết hoa cả chữ `a` đứng sau số `10`, điều thường KHÔNG phải ý muốn khi xử lý mã lớp học. Đề yêu cầu tự cài đặt đúng theo ranh giới là khoảng trắng, để tránh đúng cái bẫy này.
2
Vẫn khuôn mẫu "duyệt một lượt + biến trạng thái" của Ví dụ 2: giữ cờ dau_tu (đang ở đầu một từ hay không), bật lại cờ mỗi khi gặp khoảng trắng.

def viet_hoa_dau_tu(s):
    ket_qua = []
    dau_tu = True
    for ch in s:
        if ch == ' ':
            ket_qua.append(ch)
            dau_tu = True
        else:
            ket_qua.append(ch.upper() if dau_tu else ch.lower())
            dau_tu = False
    return ''.join(ket_qua)

4
Ranh giới từ theo đúng nghĩa bài toán là khoảng trắng, không phải "kí tự không phải chữ cái" như title() mặc định — nên chỉ cần một cờ bật lại đúng lúc gặp dấu cách, không cần quan tâm kí tự đó là chữ hay số.
5
Với "tin hoc lop 10": sau mỗi dấu cách, cờ dau_tu bật lại, nên chữ đầu của "tin", "hoc", "lop", "10" đều được viết hoa (với "10", kí tự '1' gọi .upper() không đổi vì không phải chữ cái). Kết quả: "Tin Hoc Lop 10".
Với `"tin hoc lop 10"`: sau mỗi dấu cách, cờ `dau_tu` bật lại, nên chữ đầu của "tin", "hoc", "lop", "10" đều được viết hoa (với `"10"`, kí tự `'1'` gọi `.upper()` không đổi vì không phải chữ cái). Kết quả: `"Tin Hoc Lop 10"`.
6
Ta có cờ dau_tu đúng bằng mệnh đề "kí tự vừa xét trước đó là khoảng trắng, hoặc đây là kí tự đầu xâu", nên ch.upper() chỉ được áp dụng đúng một lần cho mỗi từ, tại kí tự đầu tiên của từ đó. Suy ra thuật toán viết hoa đúng mọi chữ cái đầu từ theo ranh giới khoảng trắng, chạy $O(n)$ . Vậy viet_hoa_dau_tu cho kết quả chính xác hơn title() với dữ liệu có lẫn chữ số.
Ta có cờ `dau_tu` đúng bằng mệnh đề "kí tự vừa xét trước đó là khoảng trắng, hoặc đây là kí tự đầu xâu", nên `ch.upper()` chỉ được áp dụng đúng một lần cho mỗi từ, tại kí tự đầu tiên của từ đó. Suy ra thuật toán viết hoa đúng mọi chữ cái đầu từ theo ranh giới khoảng trắng, chạy $O(n)$. Vậy `viet_hoa_dau_tu` cho kết quả chính xác hơn `title()` với dữ liệu có lẫn chữ số.

Bước 0: trạng thái ban đầu, con trỏ i=0 ở đầu và j=5 ở cuối.

Bước 1: đổi chỗ i=0 và j=5 (T ↔ C), rồi i tăng lên 1, j giảm xuống 4.

Bước 3: đổi chỗ i=2 và j=3 (N ↔ H); nay i=3 không còn nhỏ hơn j=2 nên dừng — kết quả COHNIT.

Bẫy thường gặp

Ba lỗi hay gặp nhất: (1) viết ket_qua = ket_qua + c bên trong vòng lặp lớn — âm thầm biến thuật toán $O(n)$ thành $O(n^2)$ mà chương trình vẫn chạy đúng, chỉ chậm; (2) thử gán s[i] = 'x' để "sửa" một kí tự của xâu — Python báo lỗi TypeError vì str không hỗ trợ gán theo chỉ số, phải chuyển qua list trước; (3) tin rằng hàm dựng sẵn như title() luôn đúng ý muốn — với dữ liệu có chữ số hoặc kí tự đặc biệt, hàm tự cài đặt theo đúng ranh giới bài toán mới đáng tin cậy.

Ba lỗi hay gặp nhất: (1) viết `ket_qua = ket_qua + c` bên trong vòng lặp lớn — âm thầm biến thuật toán $O(n)$ thành $O(n^2)$ mà chương trình vẫn chạy đúng, chỉ chậm; (2) thử gán `s[i] = 'x'` để "sửa" một kí tự của xâu — Python báo lỗi `TypeError` vì `str` không hỗ trợ gán theo chỉ số, phải chuyển qua `list` trước; (3) tin rằng hàm dựng sẵn như `title()` luôn đúng ý muốn — với dữ liệu có chữ số hoặc kí tự đặc biệt, hàm tự cài đặt theo đúng ranh giới bài toán mới đáng tin cậy.

Luyện tập có hướng dẫn

Luyện tập độc lập

Ghi nhớ

Xâu Python bất biến, nên nối chuỗi từng bước trong vòng lặp âm thầm biến $O(n)$ thành $O(n^2)$ . Cách an toàn: gom kết quả vào một list, join một lần. Mẫu "duyệt một lượt, giữ một biến trạng thái nhỏ" (cờ khoảng trắng, cờ đầu từ) dùng lại được cho rất nhiều bài xử lý xâu khác, không riêng gì ba ví dụ ở đây.

Xâu Python bất biến, nên nối chuỗi từng bước trong vòng lặp âm thầm biến $O(n)$ thành $O(n^2)$. Cách an toàn: gom kết quả vào một `list`, `join` một lần. Mẫu "duyệt một lượt, giữ một biến trạng thái nhỏ" (cờ khoảng trắng, cờ đầu từ) dùng lại được cho rất nhiều bài xử lý xâu khác, không riêng gì ba ví dụ ở đây.

Bài tiếp theo vẫn dùng đúng kỹ thuật duyệt một lượt này, nhưng gắn thêm một cấu trúc đếm để phân tích tần suất kí tự trong xâu — nền tảng cho hàng loạt bài toán xâu kinh điển như kiểm tra hoán vị chữ cái.