[Rust] Bottom-up DP with explanations, O(m*n) time, O(n) space. (0 ms, faster than 100%.)
Solution\n\nrust\nimpl Solution {\n    pub fn min_distance(word1: String, word2: String) -> i32 {\n        // Treat characters as raw bytes, as it allows us to 
#### Solution\n\n```rust\nimpl Solution {\n    pub fn min_distance(word1: String, word2: String) -> i32 {\n        // Treat characters as raw bytes, as it allows us to directly access the underlying arrays:\n        let (word1, word2) = (word1.as_bytes(), word2.as_bytes());\n\n        // Allocate memory in one-go, as it is typically faster:\n        let mut dist = Vec::with_capacity(word2.len() + 1);\n\n        // Base case: we need to delete j characters in word2 in order to match the empty string word1:\n        for j in 0..=word2.len() {\n            dist.push(j)\n        }\n\n        // Use a second vector to store distances for i - 1.\n\t\t// This uses less memory than having a matrix of size (m, n), \n\t\t// and we always just use the previous row in the matrix anyway:\n        let mut prev_dist = dist.clone();\n\n        for i in 1..=word1.len() {\n            for j in 0..=word2.len() {\n                if j == 0 {\n                    dist[j] += 1; // Base case: we need to insert a character in order to match word1.\n                } else if word1[i - 1] == word2[j - 1] {\n                    // No difference, don\'t increment the edit distance:\n                    dist[j] = prev_dist[j - 1];\n                } else {\n                    // Either insert, delete or replace a character: increment the edit distance by one:\n                    dist[j] = dist[j].min(dist[j - 1]).min(prev_dist[j - 1]) + 1;\n                }\n            }\n            prev_dist.copy_from_slice(&dist); // Backup the distances for this row using memcpy.\n        }\n        dist[word2.len()] as i32\n    }\n}\n```\n\nThis algorithm gradually calculates the edit distance by iterating over the characters of the two provided words. `dist` and `prev_dist` represent two consecutive rows in the following distances matrix:\n\n<img src="https://assets.leetcode.com/users/marccarre/image_1590915262.png" width="180px" />\n\n#### Performance\n\n> Runtime: 0 ms, faster than 100.00% of Rust online submissions for Edit Distance.\n> Memory Usage: 2.1 MB, less than 100.00% of Rust online submissions for Edit Distance.\n
['Dynamic Programming', 'Rust']