Bài toán Reverse String - Đảo ngược chuỗi ký tự

Định nghĩa bài toán

Cho một chuỗi ký tự (hoặc mảng ký tự), hãy đảo ngược thứ tự các ký tự trong chuỗi mà không sử dụng thêm bộ nhớ ngoài nếu có thể. Kết quả trả về là chuỗi đã được đảo ngược.

Ví dụ:

Đầu vào: "hello" → Đầu ra: "olleh"

Đầu vào: "A man" → Đầu ra: "nam A"

Đầu vào: "" → Đầu ra: ""

Đầu vào: "a" → Đầu ra: "a"

Ràng buộc:

Chuỗi có thể chứa chữ cái, số, dấu cách, hoặc ký tự đặc biệt.

Một số biến thể yêu cầu đảo ngược tại chỗ (in-place), tức là không sử dụng bộ nhớ phụ.

Độ dài chuỗi có thể từ 0 đến 10^5.

Các cách tiếp cận giải quyết

Bài toán này có thể được giải bằng nhiều phương pháp, từ cách đơn giản sử dụng thư viện đến các cách tối ưu hóa bộ nhớ hoặc sử dụng đệ quy. Dưới đây là các cách tiếp cận phổ biến:

1. Sử dụng thư viện (Cách đơn giản nhất)

Trong các ngôn ngữ lập trình như Python, chuỗi có thể được đảo ngược dễ dàng bằng cách sử dụng các hàm có sẵn hoặc slicing.

Thuật toán:

Sử dụng slicing [::-1] trong Python hoặc các hàm đảo ngược tương tự trong các ngôn ngữ khác.

Trả về chuỗi kết quả.

def reverseString(s: str) -> str:
    return s[::-1]

Ưu điểm: Ngắn gọn, dễ hiểu, nhanh chóng.

Nhược điểm: Không thực sự thể hiện kỹ năng thuật toán, không phù hợp trong phỏng vấn yêu cầu giải pháp thủ công.

Độ phức tạp:

Thời gian: O(n) (do slicing tạo bản sao chuỗi).

Không gian: O(n) (lưu trữ chuỗi mới).

2. Sử dụng hai con trỏ (Two Pointers)

Đây là cách tiếp cận phổ biến và hiệu quả, đặc biệt khi yêu cầu đảo ngược tại chỗ (in-place) trên mảng ký tự.

Thuật toán:

Khởi tạo hai con trỏ: left ở đầu chuỗi và right ở cuối chuỗi.

Trong khi left < right:

Hoán đổi ký tự tại vị trí left và right.

Tăng left và giảm right.

Trả về chuỗi đã đảo ngược.

def reverseString(s: list[str]) -> None:
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

Ưu điểm: Tối ưu bộ nhớ (O(1) không gian phụ nếu làm trên mảng), dễ hiểu, phù hợp với yêu cầu in-place.

Nhược điểm: Cần chuyển chuỗi thành mảng ký tự trong một số ngôn ngữ (như Python, vì chuỗi là bất biến).

Độ phức tạp:

Thời gian: O(n/2) ≈ O(n).

Không gian: O(1) nếu làm trên mảng, O(n) nếu cần chuyển từ chuỗi sang mảng.

3. Sử dụng Stack

Sử dụng cấu trúc dữ liệu stack (ngăn xếp) để đảo ngược chuỗi dựa trên đặc tính "vào sau, ra trước" (LIFO).

Thuật toán:

Đẩy từng ký tự của chuỗi vào stack.

Lấy từng ký tự ra từ stack để tạo chuỗi mới.

Trả về chuỗi kết quả.

def reverseString(s: str) -> str:
    stack = []
    for char in s:
        stack.append(char)
    result = ""
    while stack:
        result += stack.pop()
    return result

Ưu điểm: Thể hiện hiểu biết về cấu trúc stack, dễ triển khai.

Nhược điểm: Tốn bộ nhớ phụ (O(n)) để lưu stack và chuỗi kết quả.

Độ phức tạp:

Thời gian: O(n) (đẩy và lấy ra khỏi stack).

Không gian: O(n) (cho stack và chuỗi kết quả).

4. Sử dụng đệ quy

Cách tiếp cận đệ quy chia bài toán thành các bài toán con để đảo ngược chuỗi.

Thuật toán:

Nếu chuỗi rỗng hoặc có một ký tự, trả về chuỗi đó.

Lấy ký tự đầu tiên, đảo ngược phần còn lại của chuỗi bằng đệ quy, rồi thêm ký tự đầu tiên vào cuối.

def reverseString(s: str) -> str:
    if len(s) <= 1:
        return s
    return reverseString(s[1:]) + s[0]

Ưu điểm: Thể hiện tư duy đệ quy, phù hợp với các ngôn ngữ hàm.

Nhược điểm: Tốn bộ nhớ ngăn xếp đệ quy (O(n)), không hiệu quả với chuỗi dài.

Độ phức tạp:

Thời gian: O(n) (mỗi ký tự được xử lý một lần).

Không gian: O(n) (do ngăn xếp đệ quy và tạo chuỗi mới).

5. Sử dụng vòng lặp đơn giản

Duyệt chuỗi từ cuối về đầu và xây dựng chuỗi mới.

Thuật toán:

Khởi tạo chuỗi kết quả rỗng.

Duyệt chuỗi từ vị trí cuối cùng về đầu, thêm từng ký tự vào chuỗi kết quả.

Trả về chuỗi kết quả.

def reverseString(s: str) -> str:
    result = ""
    for i in range(len(s) - 1, -1, -1):
        result += s[i]
    return result

Ưu điểm: Đơn giản, dễ hiểu, không cần cấu trúc dữ liệu phụ.

Nhược điểm: Tốn bộ nhớ phụ (O(n)) để lưu chuỗi kết quả.

Độ phức tạp:

Thời gian: O(n).

Không gian: O(n).

Ứng dụng thực tế

Xử lý văn bản: Đảo ngược chuỗi được dùng trong các ứng dụng như kiểm tra palindrome, xử lý dữ liệu văn bản, hoặc mã hóa.

Trình biên dịch: Phân tích cú pháp hoặc xử lý chuỗi ký tự trong mã nguồn.

Trò chơi và giáo dục: Dùng trong các bài toán logic hoặc trò chơi liên quan đến chuỗi.

Phỏng vấn kỹ thuật: Kiểm tra khả năng tư duy thuật toán, tối ưu hóa, và sử dụng cấu trúc dữ liệu cơ bản.