Khoảng cách chỉnh sửa

Bài học 9 trên 15 trong khóa học Nhập môn quy hoạch động của Coddy.

Khoảng cách chỉnh sửa, còn gọi là khoảng cách Levenshtein, là thước đo dùng để đo sự khác biệt giữa hai chuỗi. Cụ thể, đây là số thao tác ít nhất cần thực hiện để chuyển đổi chuỗi này thành chuỗi kia.

Các thao tác có thể thực hiện gồm:

Chèn: Thêm một ký tự vào một trong hai chuỗi
Xóa: Xóa một ký tự khỏi một trong hai chuỗi
Thay thế: Thay một ký tự trong một chuỗi bằng ký tự khác

Khoảng cách chỉnh sửa được sử dụng rộng rãi trong các lĩnh vực như xử lý ngôn ngữ tự nhiên, thị giác máy tính và tin sinh học.

Có thể dùng quy hoạch động để tính khoảng cách chỉnh sửa giữa hai chuỗi một cách hiệu quả.

Thử thách

Trung bình

Viết một hàm Python edit_distance nhận vào hai chuỗi và trả về khoảng cách chỉnh sửa giữa chúng.

Ví dụ:

edit_distance("kitten", "sitting") sẽ trả về 3
edit_distance("intention", "execution") sẽ trả về 5

Tự làm thử

def edit_distance(str1, str2):
    # Viết code ở đây

Tất cả bài học trong Nhập môn quy hoạch động

1Giới thiệu về quy hoạch động

Quy hoạch động là gì?Vì sao quy hoạch động quan trọng?Ứng dụng trong nhiều lĩnh vực

4Chủ đề nâng cao

Độ dài mảng con nhỏ nhất Cắt tỉa Tối ưu hóa bộ nhớ Mặt nạ bit

2Khái niệm cơ bản

Ghi nhớ kết quả Ghi nhớ kết quả không dùng đệ quy

5Tổng kết

Ôn tập các khái niệm chính Tóm tắt

3Thuật toán quy hoạch động

Dãy con chung dài nhất Bài toán cái ba lô Bài toán đổi tiềnKhoảng cách chỉnh sửa

Tự luyện tập: Trình biên dịch Python online