lunaris_engine 0.1.0

A collection of efficient algorithms implemented in Rust for real-world projects.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

//! Edit Distance (Levenshtein Distance, Unicode-safe, Production-Grade)
//!
//! Computes the minimum edit distance between two string slices.
//!
//! # Arguments
//! * `a` - The first string slice.
//! * `b` - The second string slice.
//!
//! # Returns
//! * `usize` - The minimum number of operations required to convert `a` into `b`.
//!
//! # Example
//! ```rust
//! use lunaris_engine::string::edit_distance::edit_distance;
//! assert_eq!(edit_distance("kitten", "sitting"), 3);
//! assert_eq!(edit_distance("flaw", "lawn"), 2);
//! assert_eq!(edit_distance("", "abc"), 3);
//! ```
pub fn edit_distance(a: &str, b: &str) -> usize {
    let a_chars: Vec<_> = a.chars().collect();
    let b_chars: Vec<_> = b.chars().collect();
    let m = a_chars.len();
    let n = b_chars.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];
    for (i, row) in dp.iter_mut().enumerate().take(m + 1) { row[0] = i; }
    for j in 0..=n { dp[0][j] = j; }
    for i in 1..=m {
        for j in 1..=n {
            if a_chars[i - 1] == b_chars[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + dp[i - 1][j - 1].min(dp[i][j - 1]).min(dp[i - 1][j]);
            }
        }
    }
    dp[m][n]
}