4
\$\begingroup\$

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. (Note that this solution works and passes all the test cases on LeetCode)

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!

\$\endgroup\$
4
  • \$\begingroup\$ Does the Rust implementation pass all the tests on LeetCode? \$\endgroup\$
    – pacmaninbw
    Jan 27 at 14:20
  • \$\begingroup\$ @pacmaninbw yes it does! :) \$\endgroup\$
    – Suhas
    Jan 27 at 16:02
  • \$\begingroup\$ So, are you looking on a review of both pieces? If yes, then you should split the question. Also, you say "something is off", is it working as expected? \$\endgroup\$
    – Bobby
    Jan 27 at 16:06
  • \$\begingroup\$ @Bobby -- I'm primarily looking for the review of the rust implementation, however as a bonus java review will also be welcome. But I'm more interested in the rust review. I provide the java version because I kind of wrote the java solution first and then translated that to rust... I thought that would help create some kind of better "mental model". When I say "something is off", I say it from an idiomatic perspective. The code itself works -- I just felt that the way I did it is potentially more java-like than rust-like? If that's even a thing? \$\endgroup\$
    – Suhas
    Jan 27 at 16:09
4
\$\begingroup\$

The first thing I noticed about both versions of your code is the plenitude of single-letter names, something you can improve upon. Incidentally, Rust uses snake_case for variables, so the compiler would have warned you about D.

Now, let's talk about the struggles I presume you have by reading the Rust code.

First of all, you probably felt forced to convert between i32 and usize all the time. The decision to return i32 instead of usize is a typical indicator of the less-than-ideal quality of LeetCode interfaces (as usual). In fact, it goes worse - impl Solution is not a good idea in Rust, and there is no reason to take the ownership of strings here. My advice here would be to perform all calculations using usize and only convert to i32 at the very end.

I assume HashMap<(i32, i32), i32> results from the lack of multi-dimensional vector support in Rust. Indeed, my first choice would be to use ndarray in this scenario, which is not available in the standard library. You can make a small wrapper for this:

struct Vec2<T> {
    elements: Vec<T>,
    n_rows: usize,
    n_columns: usize,
}

and derive Index<(usize, usize)> and IndexMut<(usize, usize)>. Or you could sacrifice some performance and use Vec<Vec<usize>>.

Instead of

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

I would simply use .as_bytes(), assuming that LeetCode doesn't consider multi-byte characters.


Here's how I reassembled everything according to the Java version: (not tested)

pub fn min_distance(word_a: String, word_b: String) -> i32 {
    let word_a = word_a.as_bytes();
    let word_b = word_b.as_bytes();

    let len_a = word_a.len();
    let len_b = word_b.len();

    let mut matrix = vec![vec![0; len_b + 1]; len_a + 1];

    for i in 0..=len_a {
        matrix[i][0] = i;
    }
    for j in 0..=len_b {
        matrix[0][j] = j;
    }

    for i in 1..=len_a {
        for j in 1..=len_b {
            matrix[i][j] = if word_a[i - 1] == word_b[j - 1] {
                matrix[i - 1][j - 1]
            } else {
                1 + matrix[i - 1][j - 1]
                    .min(matrix[i - 1][j])
                    .min(matrix[i][j - 1])
            };
        }
    }

    matrix[len_a][len_b] as i32
}

The restriction of LeetCode (poor interface, no external crates) caused me to be lazy, so I used nested Vecs. In a real-world scenario, ndarray::Array2 would be a far better choice.

Besides, this is still far from optimal for Rust, where we tend to avoid manual indexing and - 1. Taking into account the algorithmic nature of this application, I won't go deeper into this.

\$\endgroup\$
3
  • \$\begingroup\$ Such a beautiful review, thank you -- I'll wait a few days before accepting it :-) \$\endgroup\$
    – Suhas
    Jan 28 at 21:12
  • \$\begingroup\$ The function signature can be improved to min_distance(word_a: &str, word_b: &str) -> i32 (it still compiles). You may have intended to change that \$\endgroup\$
    – 6005
    Jan 29 at 23:01
  • 1
    \$\begingroup\$ @6005 I would have gone ahead and changed it to (&str, &str) -> usize - but the interface is a restriction of LeetCode, so I left it as is. \$\endgroup\$
    – L. F.
    Jan 30 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.