[−][src]Function leetcode_for_rust::cd0072_edit_distance::min_distance
pub fn min_distance(word1: String, word2: String) -> i32
Solutions
Approach 1: Dynamic Programming
-
Time complexity: O(m*n)
-
Space complexity: O(m*n)
-
Runtime: 4 ms
-
Memory: 4.5 MB
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
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 } }