Поиск идиоматической реализации минимального расстояния редактирования в Rust (LeetCode # 72)

Я решаю задачи динамического программирования 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"));
    }
}

Что-то в моем решении на Rust мне кажется неприятным. Не совсем уверен, но вот некоторые из моих раздражений:

1. Я не мог найти лучшего способа перебрать строку и легко ссылаться на нее по ее индексу, кроме как преобразовать ее в вектор.

2. я думаю что я unwrap()слишком много. Хотя я здесь не нацелен на кодовый гольф, подсознательно все же кажется, что я мог бы избежать стольких unwrap()с.

3. Мне немного не по себе, потому что я как бы дословно перевел свое решение с Java … возможно, есть более идиоматический способ сделать то, что я сделал?

Жду ваших советов и помощи 🙂 Заранее благодарим!

Первое, что я заметил в обеих версиях вашего кода, — это обилие однобуквенных имен, что вы можете улучшить. Между прочим, Rust использует snake_case для переменных, поэтому компилятор предупредит вас о D.

Теперь давайте поговорим о проблемах, с которыми, как я полагаю, вы сталкиваетесь, читая код Rust.

Во-первых, вы, вероятно, почувствовали необходимость конвертировать между i32 и usize все время. Решение вернуться i32 вместо того usize — типичный показатель неидеального качества интерфейсов LeetCode (как обычно). На самом деле дела обстоят хуже — impl Solution — не лучшая идея в Rust, и здесь нет причин брать на себя права собственности на строки. Мой совет здесь — выполнять все вычисления, используя usize и конвертировать только в i32 в самом конце.

Я предполагаю HashMap<(i32, i32), i32> является результатом отсутствия поддержки многомерных векторов в Rust. На самом деле, мой первый выбор — использовать ndarray в этом сценарии, которого нет в стандартной библиотеке. Для этого можно сделать небольшую обертку:

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

и получить Deref<(usize, usize)> и это DerefMut аналог. Или вы можете пожертвовать производительностью и использовать 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 (плохой интерфейс, отсутствие внешних ящиков) заставило меня полениться, поэтому я использовал вложенные Vecс. В реальном сценарии ndarray::Array2 было бы гораздо лучшим выбором.

Кроме того, это все еще далеко не оптимально для Rust, где мы стараемся избегать ручной индексации и - 1. Учитывая алгоритмический характер этого приложения, я не буду углубляться в это.