impl Solution {
    fn min_distance(word1: String, word2: String) -> i32 {
        let m = word1.len();
        let n = word2.len();

        // Create a 2D vector to store the minimum number of operations
        let mut dp = vec![vec![0; n + 1]; m + 1];

        // Fill the first row and column of the dp vector
        for i in 1..=m {
            dp[i][0] = i as i32;
        }
        for j in 1..=n {
            dp[0][j] = j as i32;
        }

        // Fill the dp vector
        for i in 1..=m {
            for j in 1..=n {
                if word1.chars().nth(i - 1) == word2.chars().nth(j - 1) {
                    // If the characters are the same, no operation is needed
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // If the characters are different, choose the minimum of insert, delete, or replace
                    dp[i][j] = 1 + dp[i][j - 1].min(dp[i - 1][j]).min(dp[i - 1][j - 1]);
                }
            }
        }

        // Return the minimum number of operations
        dp[m][n]
    }
}