Bài 3.24. Bài tập xử lý chuỗi Python: tìm ký tự lặp

Chào mừng các bạn quay trở lại với series bài tập Python! Trong thế giới lập trình, việc xử lý chuỗi là một kỹ năng cực kỳ quan trọng. Chuỗi ký tự có mặt ở khắp mọi nơi: từ tên người dùng, mật khẩu, nội dung văn bản, đến các định dạng dữ liệu như JSON hay XML. Một trong những bài toán cơ bản nhưng cũng không kém phần thú vị liên quan đến chuỗi là tìm ra các ký tự bị lặp lại (xuất hiện nhiều hơn một lần) trong một chuỗi cho trước.

Bài toán này không chỉ giúp rèn luyện tư duy logic mà còn là cơ hội để chúng ta khám phá và vận dụng các cấu trúc dữ liệu khác nhau trong Python. Hãy cùng đi sâu vào các phương pháp để giải quyết vấn đề này nhé!

Vấn đề đặt ra

Cho một chuỗi ký tự bất kỳ, ví dụ: s = "fullhousedev programming". Nhiệm vụ của chúng ta là viết một chương trình Python để xác định và liệt kê tất cả các ký tự xuất hiện nhiều hơn một lần trong chuỗi này. Trong ví dụ trên, các ký tự lặp lại là: 'l', 'u', 'o', 'e', 'r', 'g', 'm'.

Chúng ta sẽ xem xét một vài cách tiếp cận khác nhau, từ đơn giản đến tối ưu hơn.

Phương pháp 1: Sử dụng Dictionary để đếm tần suất

Đây là một cách tiếp cận trực quan và khá phổ biến. Ý tưởng là duyệt qua từng ký tự trong chuỗi và sử dụng một dictionary để lưu trữ số lần xuất hiện (tần suất) của mỗi ký tự.

Khởi tạo một dictionary rỗng, ví dụ char_counts.
Duyệt qua từng ký tự char trong chuỗi đầu vào s.
Với mỗi char:
- Nếu char đã có trong char_counts, tăng giá trị (số đếm) của nó lên 1.
- Nếu char chưa có trong char_counts, thêm char vào dictionary với giá trị là 1.
Sau khi duyệt xong chuỗi, duyệt qua dictionary char_counts. Những ký tự nào có giá trị (số đếm) lớn hơn 1 chính là các ký tự lặp lại.

def tim_ky_tu_lap_dict(chuoi_dau_vao):
    """
    Tìm ký tự lặp lại trong chuỗi sử dụng Dictionary.

    Args:
        chuoi_dau_vao: Chuỗi ký tự cần kiểm tra.

    Returns:
        Một list chứa các ký tự lặp lại (không trùng lặp trong kết quả).
    """
    char_counts = {} # 1. Khởi tạo dictionary rỗng
    ky_tu_lap = []

    # 2 & 3. Duyệt chuỗi và đếm tần suất
    for char in chuoi_dau_vao:
        # Tăng bộ đếm nếu ký tự đã tồn tại, ngược lại khởi tạo là 1
        char_counts[char] = char_counts.get(char, 0) + 1

    # 4. Lọc ra các ký tự có số đếm > 1
    for char, count in char_counts.items():
        if count > 1:
            ky_tu_lap.append(char)

    return ky_tu_lap

# Ví dụ sử dụng
s = "fullhousedev programming"
ket_qua_dict = tim_ky_tu_lap_dict(s)
print(f"Sử dụng Dictionary:")
print(f"Chuỗi đầu vào: '{s}'")
print(f"Các ký tự lặp lại: {ket_qua_dict}")
# Kết quả dự kiến (thứ tự có thể khác): ['l', 'u', 'o', 'e', 'd', 'r', 'g', 'm']
# Lưu ý: Chúng ta cũng có thể trả về một set thay vì list để đảm bảo không trùng lặp
# và không phụ thuộc vào thứ tự.

Giải thích code:

char_counts = {}: Tạo một dictionary trống để lưu trữ ký tự: số_lần_xuất_hiện.
for char in chuoi_dau_vao:: Vòng lặp này duyệt qua từng ký tự trong chuỗi chuoi_dau_vao.
char_counts[char] = char_counts.get(char, 0) + 1: Đây là một cách viết thanh lịch trong Python.
- char_counts.get(char, 0): Lấy giá trị hiện tại của char trong char_counts. Nếu char chưa có trong dictionary, nó sẽ trả về giá trị mặc định là 0.
- + 1: Tăng giá trị lấy được lên 1.
- char_counts[char] = ...: Gán giá trị mới (đã tăng) lại cho char trong dictionary.
for char, count in char_counts.items():: Duyệt qua các cặp (key, value) (tức là (ký tự, số_lần_xuất_hiện)) trong dictionary char_counts.
if count > 1:: Kiểm tra xem số lần xuất hiện có lớn hơn 1 không.
ky_tu_lap.append(char): Nếu lớn hơn 1, thêm ký tự đó vào danh sách kết quả ky_tu_lap.

Ưu điểm: Rõ ràng, dễ hiểu, cung cấp luôn cả số lần xuất hiện của mỗi ký tự nếu cần. Nhược điểm: Cần thêm một vòng lặp nữa để lọc kết quả sau khi đã đếm xong.

Phương pháp 2: Sử dụng Set để theo dõi ký tự đã thấy và ký tự lặp

Phương pháp này tập trung vào việc chỉ xác định sự tồn tại của ký tự lặp, không cần đếm chính xác số lần. Chúng ta sẽ dùng hai set:

seen: Lưu trữ tất cả các ký tự đã gặp khi duyệt chuỗi.
duplicates: Lưu trữ các ký tự đã được xác định là lặp lại (chỉ thêm vào lần đầu tiên phát hiện lặp).

Cách thực hiện:

Khởi tạo hai set rỗng: seen = set() và duplicates = set().
Duyệt qua từng ký tự char trong chuỗi đầu vào s.
Với mỗi char:
- Nếu char đã có trong seen: Điều này có nghĩa là char đã xuất hiện trước đó => nó là một ký tự lặp. Thêm char vào set duplicates.
- Bất kể char có trong seen hay không, luôn thêm char vào seen để đánh dấu là đã gặp nó.
Sau khi duyệt xong, duplicates sẽ chứa tất cả các ký tự lặp lại (mỗi ký tự chỉ xuất hiện một lần trong set này).

def tim_ky_tu_lap_set(chuoi_dau_vao):
    """
    Tìm ký tự lặp lại trong chuỗi sử dụng hai Set.

    Args:
        chuoi_dau_vao: Chuỗi ký tự cần kiểm tra.

    Returns:
        Một set chứa các ký tự lặp lại.
    """
    seen = set()       # Set để lưu các ký tự đã gặp
    duplicates = set() # Set để lưu các ký tự lặp lại

    # Duyệt qua từng ký tự
    for char in chuoi_dau_vao:
        if char in seen:
            # Nếu đã thấy ký tự này -> nó là ký tự lặp
            duplicates.add(char)
        # Đánh dấu là đã thấy ký tự này
        seen.add(char)

    return duplicates

# Ví dụ sử dụng
s = "fullhousedev programming"
ket_qua_set = tim_ky_tu_lap_set(s)
print(f"\nSử dụng Set:")
print(f"Chuỗi đầu vào: '{s}'")
# Vì set không có thứ tự, chuyển thành list để in dễ nhìn hơn (nhưng bản chất là set)
print(f"Các ký tự lặp lại: {list(ket_qua_set)}")
# Kết quả dự kiến (thứ tự không đảm bảo): ['l', 'u', 'o', 'e', 'd', 'r', 'g', 'm']

Giải thích code:

seen = set(): Tạo set rỗng để ghi nhớ các ký tự đã xuất hiện ít nhất một lần.
duplicates = set(): Tạo set rỗng để chứa các ký tự được xác định là lặp lại. Lợi ích của set ở đây là nó tự động xử lý việc một ký tự lặp nhiều lần (ví dụ 'l' xuất hiện 3 lần) chỉ được thêm vào duplicates một lần duy nhất.
if char in seen:: Kiểm tra xem ký tự char đã từng xuất hiện trước đó chưa (tức là đã có trong seen hay chưa). Việc kiểm tra in trong set rất nhanh (trung bình O(1)).
duplicates.add(char): Nếu char đã có trong seen, thêm nó vào set duplicates.
seen.add(char): Luôn luôn thêm char vào seen sau khi kiểm tra, để đánh dấu lần xuất hiện này (hoặc lần đầu tiên) của nó.

Ưu điểm: Thường hiệu quả hơn về bộ nhớ và tốc độ so với dictionary nếu chỉ cần biết ký tự nào lặp lại mà không cần số lần lặp. Thao tác in và add trên set rất nhanh. Chỉ cần một vòng lặp chính. Nhược điểm: Không cung cấp thông tin về số lần lặp của mỗi ký tự.

Phương pháp 3: Sử dụng `collections.Counter` - Cách Pythonic!

Python có một module collections rất mạnh mẽ, và bên trong đó có lớp Counter được thiết kế chuyên biệt cho việc đếm các đối tượng hashable (như ký tự trong chuỗi). Đây thường là cách ngắn gọn và hiệu quả nhất trong Python.

Import lớp Counter từ module collections.
Tạo một đối tượng Counter từ chuỗi đầu vào. Thao tác này sẽ tự động đếm tần suất của từng ký tự.
Duyệt qua đối tượng Counter và lọc ra những ký tự có số đếm lớn hơn 1.

from collections import Counter # 1. Import Counter

def tim_ky_tu_lap_counter(chuoi_dau_vao):
    """
    Tìm ký tự lặp lại trong chuỗi sử dụng collections.Counter.

    Args:
        chuoi_dau_vao: Chuỗi ký tự cần kiểm tra.

    Returns:
        Một list chứa các ký tự lặp lại.
    """
    # 2. Tạo đối tượng Counter, tự động đếm tần suất
    char_counts = Counter(chuoi_dau_vao)

    # 3. Lọc các ký tự có số đếm > 1 sử dụng List Comprehension
    ky_tu_lap = [char for char, count in char_counts.items() if count > 1]

    return ky_tu_lap

# Ví dụ sử dụng
s = "fullhousedev programming"
ket_qua_counter = tim_ky_tu_lap_counter(s)
print(f"\nSử dụng collections.Counter:")
print(f"Chuỗi đầu vào: '{s}'")
print(f"Các ký tự lặp lại: {ket_qua_counter}")
# Kết quả dự kiến (thứ tự có thể khác, thường theo thứ tự xuất hiện đầu tiên):
# ['l', 'u', 'o', 'e', 'd', 'r', 'g', 'm']

Giải thích code:

from collections import Counter: Import lớp Counter cần thiết.
char_counts = Counter(chuoi_dau_vao): Đây là điểm mấu chốt. Chỉ cần truyền chuỗi vào Counter(), Python sẽ tự động thực hiện việc đếm tần suất và tạo ra một đối tượng giống dictionary ({ký_tự: số_lần_xuất_hiện, ...}). Ví dụ, với s = "banana", Counter(s) sẽ là Counter({'a': 3, 'n': 2, 'b': 1}).
ky_tu_lap = [char for char, count in char_counts.items() if count > 1]: Đây là một list comprehension - cách viết gọn gàng để tạo list. Nó tương đương với:
```
# ky_tu_lap = []
# for char, count in char_counts.items():
#     if count > 1:
#         ky_tu_lap.append(char)
```
Nó duyệt qua các cặp (ký_tự, số_đếm) trong char_counts và chỉ giữ lại những ký_tự (char) mà số_đếm (count) lớn hơn 1.

Ưu điểm: Cực kỳ ngắn gọn, dễ đọc (khi đã quen), hiệu quả (thường được tối ưu hóa ở cấp độ C), và rất "Pythonic" (phù hợp với phong cách lập trình của Python). Nhược điểm: Cần phải import module collections.

Phương pháp 4: Sử dụng Vòng lặp lồng nhau (Brute Force - Ít hiệu quả)

Cách này ít được khuyến khích vì hiệu suất kém, nhưng đáng để biết như một giải pháp cơ bản nhất.

Duyệt qua chuỗi bằng vòng lặp for với chỉ số i.
Bên trong, dùng một vòng lặp for khác với chỉ số j, bắt đầu từ i + 1.
So sánh ký tự tại s[i] và s[j]. Nếu chúng giống nhau, thì s[i] là một ký tự lặp.
Sử dụng một set để lưu kết quả nhằm tránh thêm cùng một ký tự lặp nhiều lần vào danh sách kết quả.

def tim_ky_tu_lap_nested(chuoi_dau_vao):
    """
    Tìm ký tự lặp lại sử dụng vòng lặp lồng nhau (ít hiệu quả).

    Args:
        chuoi_dau_vao: Chuỗi ký tự cần kiểm tra.

    Returns:
        Một set chứa các ký tự lặp lại.
    """
    n = len(chuoi_dau_vao)
    duplicates = set() # Dùng set để tránh trùng lặp trong kết quả

    for i in range(n):
        for j in range(i + 1, n): # Chỉ so sánh với các ký tự đứng sau
            if chuoi_dau_vao[i] == chuoi_dau_vao[j]:
                duplicates.add(chuoi_dau_vao[i])
                # Có thể break vòng lặp trong nếu chỉ cần biết nó lặp lại
                # break
    return duplicates

# Ví dụ sử dụng
s = "fullhousedev programming"
ket_qua_nested = tim_ky_tu_lap_nested(s)
print(f"\nSử dụng vòng lặp lồng nhau:")
print(f"Chuỗi đầu vào: '{s}'")
print(f"Các ký tự lặp lại: {list(ket_qua_nested)}") # Chuyển sang list để in
# Kết quả dự kiến (thứ tự không đảm bảo): ['l', 'u', 'o', 'e', 'd', 'r', 'g', 'm']

Giải thích code:

Vòng lặp ngoài for i in range(n): Duyệt qua từng ký tự từ đầu đến cuối.
Vòng lặp trong for j in range(i + 1, n): Duyệt qua các ký tự đứng sau ký tự i. Việc bắt đầu từ i + 1 giúp tránh so sánh một ký tự với chính nó và tránh lặp lại các cặp đã so sánh (ví dụ: không cần so sánh s[1] với s[0] nếu đã so sánh s[0] với s[1]).
if chuoi_dau_vao[i] == chuoi_dau_vao[j]:: Nếu tìm thấy hai ký tự giống nhau ở vị trí khác nhau.
duplicates.add(chuoi_dau_vao[i]): Thêm ký tự đó vào set kết quả.

Ưu điểm: Logic đơn giản, không cần cấu trúc dữ liệu phức tạp (ngoại trừ set để lưu kết quả). Nhược điểm: Rất chậm với các chuỗi dài. Độ phức tạp thời gian là O(n^2), trong khi các phương pháp dùng dictionary/set/Counter thường là O(n). Không nên sử dụng trong thực tế cho chuỗi lớn.

Xử lý các trường hợp đặc biệt (Ví dụ: Phân biệt chữ hoa/thường)

Các phương pháp trên mặc định sẽ phân biệt chữ hoa và chữ thường (ví dụ: 'a' và 'A' là khác nhau). Nếu bạn muốn coi chúng là một, bạn có thể chuyển đổi toàn bộ chuỗi về chữ hoa hoặc chữ thường trước khi xử lý:

s_goc = "Programming Is Fun"
s_thuong = s_goc.lower() # Chuyển thành "programming is fun"
s_hoa = s_goc.upper()   # Chuyển thành "PROGRAMMING IS FUN"

print(f"Chuỗi gốc: '{s_goc}'")
print(f"Ký tự lặp (phân biệt hoa/thường): {tim_ky_tu_lap_counter(s_goc)}")
# Kết quả: ['r', 'g', 'm', 'i', 'n']

print(f"Chuỗi thường: '{s_thuong}'")
print(f"Ký tự lặp (không phân biệt hoa/thường): {tim_ky_tu_lap_counter(s_thuong)}")
# Kết quả: ['p', 'r', 'o', 'g', 'm', 'i', 'n', ' '] (lưu ý cả dấu cách cũng lặp)

Bạn cũng có thể muốn bỏ qua các ký tự đặc biệt hoặc khoảng trắng. Điều này có thể thực hiện bằng cách lọc chuỗi trước khi đưa vào các hàm tìm kiếm:

import string # Module chứa các hằng số chuỗi hữu ích

def loc_chuoi(chuoi):
    """Chỉ giữ lại các chữ cái và chuyển thành chữ thường"""
    chuoi_sach = ""
    for char in chuoi:
        if char.isalpha(): # Kiểm tra xem có phải là chữ cái không
            chuoi_sach += char.lower()
    return chuoi_sach

s_phuc_tap = "Hello World! 123 Hello again."
s_da_loc = loc_chuoi(s_phuc_tap) # "helloworldhelloagain"

print(f"\nChuỗi phức tạp: '{s_phuc_tap}'")
print(f"Chuỗi sau khi lọc: '{s_da_loc}'")
print(f"Ký tự lặp (chỉ chữ cái, không phân biệt hoa/thường): {tim_ky_tu_lap_counter(s_da_loc)}")
# Kết quả: ['h', 'e', 'l', 'o', 'w', 'r', 'd', 'a', 'g', 'i', 'n']

Vậy là chúng ta đã cùng nhau khám phá các cách khác nhau để giải quyết bài toán tìm ký tự lặp trong chuỗi bằng Python. Mỗi phương pháp có ưu và nhược điểm riêng, nhưng collections.Counter thường là lựa chọn tối ưu và Pythonic nhất cho bài toán đếm tần suất và tìm phần tử lặp. Hi vọng bài viết này giúp bạn củng cố kiến thức về xử lý chuỗi và các cấu trúc dữ liệu trong Python!

Comments

There are no comments at the moment.