Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Khoảng cách chỉnh sửa Levenshtein

    Cho hai xâu aaa và bbb (chỉ gồm chữ cái thường, không khoảng trắng). Tính khoảng cách chỉnh sửa (số phép chèn / xóa / thay thế một ký tự ít nhất để biến aaa thành bbb).

    Nếu một xâu rỗng thì khoảng cách bằng độ dài xâu còn lại.

    • Định dạng đầu vào:

      Dòng 1: xâu aaa (có thể rỗng). Dòng 2: xâu bbb (có thể rỗng).

    • Ràng buộc đầu vào:

      0≤∣a∣,∣b∣≤20000 \le |a|, |b| \le 20000≤∣a∣,∣b∣≤2000, chỉ gồm ký tự a–z.

    • Định dạng đầu ra:

      Một số nguyên: khoảng cách chỉnh sửa.

    Ví dụ:

    Đầu vào:

    kitten
sitting

    Đầu ra:

    3

    Giải thích:

    kitten→sitten (thay k→s), →sittin (thay e→i), →sitting (chèn g): 3 phép.

    Đang tải editor...