CSES - Edit Distance | Khoảng cách chỉnh sửa

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

NguyenHuuNhatQuang , Flower_On_Stone , kitsune

Dạng bài

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Khoảng cách chỉnh sửa giữa hai xâu là số lượng thao tác tối thiểu cần thiết để chuyển đổi một xâu thành xâu kia.

Các thao tác được phép là:

Thêm một ký tự vào xâu.
Xóa một ký tự khỏi xâu.
Thay thế một ký tự trong xâu.

Ví dụ: khoảng cách chỉnh sửa giữa LOVE và MOVIE là \(2\), vì trước tiên bạn có thể thay thế L bằng M, sau đó thêm I.

Nhiệm vụ của bạn là tính toán khoảng cách chỉnh sửa giữa hai xâu.

Input

Dòng đầu tiên có một xâu chứa \(n\) ký tự trong khoảng từ A–Z.
Dòng thứ hai có một xâu chứa các ký tự \(m\) trong khoảng từ A–Z.

Output

In một số nguyên: khoảng cách chỉnh sửa giữa các xâu.

Constraints

\(1 \leq n \leq 5000\)

Example

Sample input

LOVE
MOVIE

Sample output

Bình luận

-3

\(\text{Code Python, nhớ dùng Pypy 2 kẻo TLE 1 đấm:}\)

Python

import sys;N,M=sys.stdin.readline(),sys.stdin.readline();n=len(N);m=len(M);dp=[[0]*(m+1)for _ in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        if i==0:dp[i][j]=j
        elif j==0:dp[i][j]=i
        elif N[i-1]==M[j-1]:dp[i][j]=dp[i-1][j-1]
        else:dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
print(dp[n][m])

1 bình luận nữa