My Life 时光荏苒,岁月如梭

字符串编辑距离算法

2020-03-24
王世东

代码实现

fn get_distance(s1: String, s2: String) -> i32 {
    let chars1 = s1.chars().collect::<Vec<char>>();
    let chars2 = s2.chars().collect::<Vec<char>>();
    let len1 = s1.chars().count();
    let len2 = s2.chars().count();
    let mut d = vec![vec![0i32; len1 + 1]; len2 + 1];
    for i in  0 .. len1 {
        d[i][0] = i as i32;
    }
    for i in  0 .. len2 {
        d[0][i] = i as i32;
    }
    for i in 1 .. len1 + 1 {
        for j in 1 .. len2 + 1 {
            let mut cost = 1;
            if chars1[i-1] == chars2[j-1] {
                cost = 0;
            }
            let delete = d[i-1][j] + 1;
            let insert = d[i][j-1] + 1;
            let substitution = d[i-1][j-1] + cost;
            d[i][j] = min(delete, insert, substitution);

        }
    }
    d[len1][len2]
}
fn min(d: i32, i: i32, s: i32) -> i32 {
    let temp = if d > i { i } else { d };
    if s < temp {
        s
    } else {
        temp
    }
}

pub fn main() {
    println!("{}", get_distance("wsdjeg".to_string(), "wdsjgh".to_string()));
}

参考资料


延生阅读

Share on:

评论