72. Edit Distance Hard

1/**
2 * [72] Edit Distance
3 *
4 * Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
5 * You have the following three operations permitted on a word:
6 * 
7 * 	Insert a character
8 * 	Delete a character
9 * 	Replace a character
10 * 
11 *  
12 * Example 1:
13 * 
14 * Input: word1 = "horse", word2 = "ros"
15 * Output: 3
16 * Explanation: 
17 * horse -> rorse (replace 'h' with 'r')
18 * rorse -> rose (remove 'r')
19 * rose -> ros (remove 'e')
20 * 
21 * Example 2:
22 * 
23 * Input: word1 = "intention", word2 = "execution"
24 * Output: 5
25 * Explanation: 
26 * intention -> inention (remove 't')
27 * inention -> enention (replace 'i' with 'e')
28 * enention -> exention (replace 'n' with 'x')
29 * exention -> exection (replace 'n' with 'c')
30 * exection -> execution (insert 'u')
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	0 <= word1.length, word2.length <= 500
36 * 	word1 and word2 consist of lowercase English letters.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/edit-distance/
42// discuss: https://leetcode.com/problems/edit-distance/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn min_distance(word1: String, word2: String) -> i32 {
48        0
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_72() {
60    }
61}
62