1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

//! Edit Distance [leetcode: edit_distance](https://leetcode.com/problems/edit-distance/)
//!
//! Given two words *word1* and *word2*, find the minimum number of operations required to convert *word1* to *word2*.
//!
//! You have the following 3 operations permitted on a word:
//! 1. Insert a character
//! 2. Delete a character
//! 3. Replace a character
//!
//! **Example1:**
//!
//! ```
//! Input: word1 = "horse", word2 = "ros"
//! Output: 3
//! Explanation:
//! horse -> rorse (replace 'h' with 'r')
//! rorse -> rose (remove 'r')
//! rose -> ros (remove 'e')
//! ```
//!
//! **Example2:**
//!
//! ```
//! 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')
//! ```
//!

/// # Solutions
///
/// # Approach 1: Dynamic Programming
///
/// * Time complexity: O(m*n)
///
/// * Space complexity: O(m*n)
///
/// * Runtime: 4 ms
/// * Memory: 4.5 MB
///
/// ```rust
/// impl Solution {
///     pub fn min_distance(word1: String, word2: String) -> i32 {
///         let word1_bytes = word1.into_bytes();
///         let word2_bytes = word2.into_bytes();
///         let m = word1_bytes.len();
///         let n = word2_bytes.len();
///         let mut dp = vec![vec![0; n + 1]; m + 1];
///
///         // number of deletions to reach word2[0]
///         for i in 0..=m { dp[i][0] = i; }
///         // to construct word2[j] just with word1[0] need to j insertions
///         for j in 0..=n { dp[0][j] = j; }
///
///         for i in 1..=m {
///             for j in 1..=n {
///                 // we can obtain word2[0..j] from word1[0..i] either by
///                 // deleting the ith charactor. knowing eg: dp[i - 1][j]
///                 // inserting the jth charactor. knowing eg: dp[i][j - 1]
///                 // or replate ith charactor with jth charactor. knowing eg: dp[i - 1][j - 1]
///                 dp[i][j] = (dp[i - 1][j - 1] + (word1_bytes[i - 1] != word2_bytes[j - 1]) as usize)
///                 .min(dp[i - 1][j] + 1)
///                 .min(dp[i][j - 1] + 1);
///             }
///         }
///         dp[m][n] as i32
///     }
/// }
/// ```
///
/// # Approach 2: Dynamic Programming
///
/// * Time complexity: O(m*n)
///
/// * Space complexity: O(m*n)
///
/// * Runtime: 4 ms
/// * Memory: 4.5 MB
///
/// ```rust
/// impl Solution {
///     pub fn min_distance(word1: String, word2: String) -> i32 {
///         let word1_bytes = word1.into_bytes();
///         let word2_bytes = word2.into_bytes();
///         let m = word1_bytes.len();
///         let n = word2_bytes.len();
///         let mut dp = vec![vec![0; n + 1]; m + 1];
///
///         // number of deletions to reach word2[0]
///         for i in 0..=m { dp[i][0] = i; }
///         // to construct word2[j] just with word1[0] need to j insertions
///         for j in 0..=n { dp[0][j] = j; }
///
///         for i in 1..=m {
///             for j in 1..=n {
///                 if word1_bytes[i - 1] == word2_bytes[j - 1] {
///                     dp[i][j] = dp[i - 1][j - 1];
///                 } else {
///                     // we can obtain word2[0..j] from word1[0..i] either by
///                     // deleting the ith charactor. knowing eg: dp[i - 1][j]
///                     // inserting the jth charactor. knowing eg: dp[i][j - 1]
///                     // or replate ith charactor with jth charactor. knowing eg: dp[i - 1][j - 1]
///                     dp[i][j] = dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]) + 1;
///                 }
///             }
///         }
///         dp[m][n] as i32
///     }
/// }
/// ```
///

pub fn min_distance(word1: String, word2: String) -> i32 {
    let word1_bytes = word1.into_bytes();
    let word2_bytes = word2.into_bytes();
    let m = word1_bytes.len();
    let n = word2_bytes.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    // number of deletions to reach word2[0]
    for i in 0..=m { dp[i][0] = i; }
    // to construct word2[j] just with word1[0] need to j insertions
    for j in 0..=n { dp[0][j] = j; }

    for i in 1..=m {
        for j in 1..=n {
            // we can obtain word2[0..j] from word1[0..i] either by
            // deleting the ith charactor. knowing eg: dp[i - 1][j]
            // inserting the jth charactor. knowing eg: dp[i][j - 1]
            // or replate ith charactor with jth charactor. knowing eg: dp[i - 1][j - 1]
            dp[i][j] = (dp[i - 1][j - 1] + (word1_bytes[i - 1] != word2_bytes[j - 1]) as usize)
            .min(dp[i - 1][j] + 1)
            .min(dp[i][j - 1] + 1);
        }
    }
    dp[m][n] as i32
}