搜索最小编辑距离(LeetCode #72)的惯用锈蚀实现

Question

我正在解决LeetCode动态编程的挑战(这个挑战是#72，在https://leetcode.com/problems/edit-distance)。

下面，我为两个字符串之间的最小编辑距离实现了一个Rust解决方案。(请注意，该解决方案在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();
    }
}

我实际上也用JAVA解决了同样的问题，我有一个更好的命令.

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

在我看来，关于我的铁锈解决方案的一些东西似乎是不存在的。不太确定，但以下是我的一些恼怒之处：

1. 除了将字符串转换为向量之外，我找不到更好的方法来迭代字符串并通过它的索引引用它。
2. 我想我是unwrap()-ing太多了。虽然我的目标不是代码高尔夫，但潜意识中我还是觉得我可以避免这么多unwrap()s。
3. 我有点难过，因为我把我的解决方案逐字逐句地从Java翻译过来.也许我所做的一切都有一种更老练的方法？

期待您的建议和帮助:-)提前谢谢！

Answer 1

关于这两个版本的代码，我注意到的第一件事是单字母名称的充分性，这是您可以改进的东西。顺便说一句，Rust使用snake_case作为变量，所以编译器会警告您注意D。

现在，让我们来谈谈我认为您通过阅读Rust代码所做的斗争。

首先，您可能一直感到不得不在i32和usize之间进行转换。返回i32而不是usize的决定是LeetCode接口质量不理想的典型指标(和往常一样)。事实上，更糟糕的是，impl Solution在Rust中不是一个好主意，没有理由在这里使用字符串的所有权。我在这里的建议是使用usize执行所有计算，并且只在最后转换为i32。

我认为HashMap<(i32, i32), i32>是由于锈蚀中缺乏多维矢量支持所致。实际上，我的第一个选择是在这个场景中使用ndarray，这在标准库中是不可用的。您可以为此做一个小包装：

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

并导出Index<(usize, usize)>和IndexMut<(usize, usize)>。或者您可以牺牲一些性能并使用Vec<Vec<usize>>。

而不是

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

我只需要使用.as_bytes()，假设LeetCode不考虑多字节字符。

下面是我如何根据Java版本重新组装所有东西：(没有测试)

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
}

LeetCode (不好的接口，没有外部板条箱)的限制使我懒惰，所以我使用嵌套的Vecs，在现实世界中，ndarray::Array2将是一个更好的选择。

此外，对于Rust来说，这还远远不是最优的，因为我们倾向于避免手工索引和- 1。考虑到这个应用程序的算法性质，我将不再深入研究这个问题。