Mô phỏng thuật toán Đảo ngược chuỗi

Reverse String · Nhóm: Chuỗi

Đảo ngược chuỗi bằng hai con trỏ: đổi chỗ ký tự đầu và cuối, rồi cùng tiến dần vào giữa cho tới khi gặp nhau.

Ý tưởng

Đặt con trỏ i ở đầu, con trỏ j ở cuối.

Đổi chỗ s[i] với s[j], rồi i tăng và j giảm.

Dừng khi i gặp hoặc vượt j; lúc đó chuỗi đã đảo xong.

Vì sao đúng

Chỉ đảo tại chỗ với bộ nhớ hằng số và số phép đổi chỗ đúng bằng một nửa độ dài, gọn và nhanh.

Mã Python

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

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.