## 72. Edit Distance

Given two strings `word1`

and `word2`

, return *the minimum number of operations required to convert word1 to word2*.

You have the following three operations permitted on a word:

- Insert a character
- Delete a character
- Replace a character

**Example 1:**

Input:word1 = "horse", word2 = "ros"Output:3Explanation:horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')

**Example 2:**

Input:word1 = "intention", word2 = "execution"Output:5Explanation:intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')

**Constraints:**

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

`word1`

and`word2`

consist of lowercase English letters.

## Rust Solution

```
struct Solution;
impl Solution {
fn min_distance(word1: String, word2: String) -> i32 {
let n = word1.len();
let m = word2.len();
let word1: Vec<char> = word1.chars().collect();
let word2: Vec<char> = word2.chars().collect();
let mut dp = vec![vec![0; m + 1]; n + 1];
for i in 0..=n {
dp[i][0] = i;
}
for j in 0..=m {
dp[0][j] = j;
}
for i in 1..=n {
for j in 1..=m {
if word1[i - 1] == word2[j - 1] {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]) + 1;
}
}
}
dp[n][m] as i32
}
}
#[test]
fn test() {
let word1 = "horse".to_string();
let word2 = "ros".to_string();
let res = 3;
assert_eq!(Solution::min_distance(word1, word2), res);
let word1 = "intention".to_string();
let word2 = "execution".to_string();
let res = 5;
assert_eq!(Solution::min_distance(word1, word2), res);
}
```

Having problems with this solution? Click here to submit an issue on github.