problem

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: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
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.

submission

// dynamic programming
impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let mut dp = (0..=word1.len())
            .map(|i| (0..=word2.len())
                .map(move |j| i.max(j))
                .collect::<Vec<_>>()
            )
            .collect::<Vec<_>>();
        for (i, b1) in word1.bytes().enumerate() {
            for (j, b2) in word2.bytes().enumerate() {
                // if b1 == b2, no extra replace operation is needed
                let extra = if b1 == b2 { 0 } else { 1 };
                dp[i + 1][j + 1] = (dp[i][j + 1] + 1) // delete 1
                    .min(dp[i + 1][j] + 1) // insert 1
                    .min(dp[i][j] + extra); // replace 1 if needed
            }
        }
        dp[word1.len()][word2.len()] as _
    }
}