Cho 2 chuỗi word1 và word2. Tính số bước ít nhất biến đổi word1 thành word2 bằng 3 thao tác: chèn, xóa, thay thế.
Ví dụ: word1 = 'horse', word2 = 'ros' -> Output: 3.
Định Dạng Đầu Vào (Input)
Dòng 1: word1
Dòng 2: word2
Dòng 2: word2
Định Dạng Đầu Ra (Output)
Số bước ít nhất
Ràng Buộc (Constraints)
0 <= word1.length, word2.length <= 500
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
"horse"
"ros"
Output:
3
Giải thích: 3 thao tác
Ví dụ 2:
Input:
"intention"
"execution"
Output:
5
Giải thích: 5 thao tác
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Levenshtein DP 2D O(m * n)
dp[i][j] = 1 + min(delete, insert, replace)
Dữ liệu đầu vào (Input):
"horse"
"ros"
Kết quả kỳ vọng (Expected Output):
3
Dữ liệu đầu vào (Input):
"intention"
"execution"
Kết quả kỳ vọng (Expected Output):
5
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
