†編集距離†

distance.rs

use std::cmp;

fn main() {
    let base: &str = "kitten";
    let changed: &str = "sitting";
    let mut dp: Vec<Vec<i8>> = vec![];
    let x_len: usize = base.len() + 1;
    let y_len: usize = changed.len() + 1;
    for _ in 0..y_len {
        let elem: Vec<i8> = vec![-1; x_len];
        dp.push(elem);
    }

    for i in 0..x_len {
        dp[0][i] = i as i8;
    }

    for i in 0..y_len {
        dp[i][0] = i as i8;
    }

    for i in 1..x_len {
        for j in 1..y_len {
            let _i: usize = i as usize;
            let _j: usize = j as usize;
            let cost = if base.chars().nth(_i - 1).unwrap() == changed.chars().nth(_j - 1).unwrap()
            {
                0
            } else {
                1
            };
            dp[_j][_i] = cmp::min(
                cmp::min(dp[_j - 1][_i] + 1, dp[_j][_i - 1] + 1),
                dp[_j - 1][_i - 1] + cost,
            );
            println!("{} {} => {}", _i, _j, dp[_j][_i]);
        }
    }

    let x: usize = x_len - 1 as usize;
    let y: usize = y_len - 1 as usize;
    println!("{}", dp[y][x]);
}