257. Edit Distance

Given two strings word1 and word2, return the minimum number of operations (insert, delete, or replace a single character) required to convert word1 into word2. Input: '"word1", "word2"'.

Input: '"word1", "word2"'.

Output: Integer — minimum edit operations.

Examples

Input: "horse", "ros"
Output: 3
Explanation: horse->rorse->rose->ros.

Input: "intention", "execution"
Output: 5
Explanation: Five operations.

Input: "", "abc"
Output: 3
Explanation: Insert three characters.

Constraints

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

Asked by