Cho hai chuỗi word1 và word2. Tìm số thao tác tối thiểu để chuyển đổi word1 thành word2. Bạn được phép thực hiện ba thao tác sau trên một từ:

• Insert a character

• Delete a character

• Replace a character

Input:

• Bao gồm hai dòng: dòng 1 chứa word1, dòng 2 chứa word2

• 0 <= word1.length, word2.length <= 500

Output:

Gồm 1 dòng chứa 1 số nguyên là số thao tác tối thiểu để chuyển đổi word1 thành word2.

Ví dụ :

Input:

horse
ros

Output:

3

Giải thích: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')