Category: News

I am solving LeetCode Dynamic Programming challenges (this one is #72, at https://leetcode.com/problems/edit-distance).

Here below, I’ve implemented a Rust solution for the minimum edit distance between two strings problem

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();
    }
}

I’ve actually also solved the same thing in JAVA, which I have a much better command on…

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int()() D = new int(m+1)(n+1);

        for(int i=0; i<=m; ++i) D(i)(0) = i;
        for(int j=0; j<=n; ++j) D(0)(j) = j;

        for(int i=1; i<=m; ++i) {
            for(int j=1; j<=n; ++j) {
                if(word1.charAt(i-1) == word2.charAt(j-1)) D(i)(j) = D(i-1)(j-1);
                else D(i)(j) = 1 + Math.min(D(i-1)(j-1), Math.min(D(i-1)(j), D(i)(j-1)));
            }
        }
        return D(m)(n);
    }

    public static void main(String() args) {
        System.out.println(minDistance("intention", "execution"));
    }
}

Something about my Rust solution seems off to me. Not really sure but here are some of my irritations:

1. I couldn’t find a better way to iterate a string and refer to it by its index easily other than having to convert it to a vector.

2. I think I’m unwrap()-ing too much. Although I’m not aiming for code golf here, it still feels subconsciously that I could have avoided so many unwrap()s.

3. I feel a bit bad because I kind of word to word translated my solution from Java… perhaps there’s a more Rust-idiomatic way of doing whatever I did?

Looking forward to your advise and help 🙂 Thanks in advance!