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:
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.
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 manyunwrap()
s.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!