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ụ :

Giải thích:

• horse -> rorse (replace 'h' with 'r')
• rorse -> rose (remove 'r')
• rose -> ros (remove 'e')