use std::collections::HashMap;
use std::cmp::min;

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let mut D: HashMap<(i32, i32), i32> = HashMap::new();
        let m = word1.len() as i32;
        let n = word2.len() as i32;

        let w1: Vec<char> = word1.chars().collect();
        let w2: Vec<char> = word2.chars().collect();

        for i in 0..=m {
            D.insert((i, 0), i);
        }
        for j in 0..=n {
            D.insert((0, j), j);
        }

        for i in 1..=m {
            for j in 1..=n {
                if w1[(i-1) as usize] == w2[(j-1) as usize] { 
                    D.insert((i, j), *D.get(&(i-1, j-1)).unwrap());
                } else {
                    let p = *D.get(&(i - 1, j - 1)).unwrap();
                    let q = *D.get(&(i - 1, j)).unwrap();
                    let r = *D.get(&(i, j - 1)).unwrap();

                    D.insert((i, j), 1 + min(p, min(q, r)));
                }
            }
        }

        return *D.get(&(m, n)).unwrap();
    }
}