leetcode_for_rust/cd0072_edit_distance/
mod.rs

1//! Edit Distance [leetcode: edit_distance](https://leetcode.com/problems/edit-distance/)
2//!
3//! Given two words *word1* and *word2*, find the minimum number of operations required to convert *word1* to *word2*.
4//!
5//! You have the following 3 operations permitted on a word:
6//! 1. Insert a character
7//! 2. Delete a character
8//! 3. Replace a character
9//!
10//! **Example1:**
11//!
12//! ```
13//! Input: word1 = "horse", word2 = "ros"
14//! Output: 3
15//! Explanation:
16//! horse -> rorse (replace 'h' with 'r')
17//! rorse -> rose (remove 'r')
18//! rose -> ros (remove 'e')
19//! ```
20//!
21//! **Example2:**
22//!
23//! ```
24//! Input: word1 = "intention", word2 = "execution"
25//! Output: 5
26//! Explanation:
27//! intention -> inention (remove 't')
28//! inention -> enention (replace 'i' with 'e')
29//! enention -> exention (replace 'n' with 'x')
30//! exention -> exection (replace 'n' with 'c')
31//! exection -> execution (insert 'u')
32//! ```
33//!
34
35/// # Solutions
36///
37/// # Approach 1: Dynamic Programming
38///
39/// * Time complexity: O(m*n)
40///
41/// * Space complexity: O(m*n)
42///
43/// * Runtime: 4 ms
44/// * Memory: 4.5 MB
45///
46/// ```rust
47/// impl Solution {
48///     pub fn min_distance(word1: String, word2: String) -> i32 {
49///         let word1_bytes = word1.into_bytes();
50///         let word2_bytes = word2.into_bytes();
51///         let m = word1_bytes.len();
52///         let n = word2_bytes.len();
53///         let mut dp = vec![vec![0; n + 1]; m + 1];
54///
55///         // number of deletions to reach word2[0]
56///         for i in 0..=m { dp[i][0] = i; }
57///         // to construct word2[j] just with word1[0] need to j insertions
58///         for j in 0..=n { dp[0][j] = j; }
59///
60///         for i in 1..=m {
61///             for j in 1..=n {
62///                 // we can obtain word2[0..j] from word1[0..i] either by
63///                 // deleting the ith charactor. knowing eg: dp[i - 1][j]
64///                 // inserting the jth charactor. knowing eg: dp[i][j - 1]
65///                 // or replate ith charactor with jth charactor. knowing eg: dp[i - 1][j - 1]
66///                 dp[i][j] = (dp[i - 1][j - 1] + (word1_bytes[i - 1] != word2_bytes[j - 1]) as usize)
67///                 .min(dp[i - 1][j] + 1)
68///                 .min(dp[i][j - 1] + 1);
69///             }
70///         }
71///         dp[m][n] as i32
72///     }
73/// }
74/// ```
75///
76/// # Approach 2: Dynamic Programming
77///
78/// * Time complexity: O(m*n)
79///
80/// * Space complexity: O(m*n)
81///
82/// * Runtime: 4 ms
83/// * Memory: 4.5 MB
84///
85/// ```rust
86/// impl Solution {
87///     pub fn min_distance(word1: String, word2: String) -> i32 {
88///         let word1_bytes = word1.into_bytes();
89///         let word2_bytes = word2.into_bytes();
90///         let m = word1_bytes.len();
91///         let n = word2_bytes.len();
92///         let mut dp = vec![vec![0; n + 1]; m + 1];
93///
94///         // number of deletions to reach word2[0]
95///         for i in 0..=m { dp[i][0] = i; }
96///         // to construct word2[j] just with word1[0] need to j insertions
97///         for j in 0..=n { dp[0][j] = j; }
98///
99///         for i in 1..=m {
100///             for j in 1..=n {
101///                 if word1_bytes[i - 1] == word2_bytes[j - 1] {
102///                     dp[i][j] = dp[i - 1][j - 1];
103///                 } else {
104///                     // we can obtain word2[0..j] from word1[0..i] either by
105///                     // deleting the ith charactor. knowing eg: dp[i - 1][j]
106///                     // inserting the jth charactor. knowing eg: dp[i][j - 1]
107///                     // or replate ith charactor with jth charactor. knowing eg: dp[i - 1][j - 1]
108///                     dp[i][j] = dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]) + 1;
109///                 }
110///             }
111///         }
112///         dp[m][n] as i32
113///     }
114/// }
115/// ```
116///
117
118pub fn min_distance(word1: String, word2: String) -> i32 {
119    let word1_bytes = word1.into_bytes();
120    let word2_bytes = word2.into_bytes();
121    let m = word1_bytes.len();
122    let n = word2_bytes.len();
123    let mut dp = vec![vec![0; n + 1]; m + 1];
124
125    // number of deletions to reach word2[0]
126    for i in 0..=m { dp[i][0] = i; }
127    // to construct word2[j] just with word1[0] need to j insertions
128    for j in 0..=n { dp[0][j] = j; }
129
130    for i in 1..=m {
131        for j in 1..=n {
132            // we can obtain word2[0..j] from word1[0..i] either by
133            // deleting the ith charactor. knowing eg: dp[i - 1][j]
134            // inserting the jth charactor. knowing eg: dp[i][j - 1]
135            // or replate ith charactor with jth charactor. knowing eg: dp[i - 1][j - 1]
136            dp[i][j] = (dp[i - 1][j - 1] + (word1_bytes[i - 1] != word2_bytes[j - 1]) as usize)
137            .min(dp[i - 1][j] + 1)
138            .min(dp[i][j - 1] + 1);
139        }
140    }
141    dp[m][n] as i32
142}
leetcode_for_rust/cd0072_edit_distance/mod.rs

leetcode_for_rust/cd0072_edit_distance/
mod.rs
