From 0a95bae451c1847f4f0b9601e60959f4e8e6b669 Mon Sep 17 00:00:00 2001 From: 魏曹先生 <1992414357@qq.com> Date: Thu, 12 Mar 2026 14:28:08 +0800 Subject: Refactor display utilities --- utils/src/math/levenshtein_distance.rs | 38 ++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) create mode 100644 utils/src/math/levenshtein_distance.rs (limited to 'utils/src/math') diff --git a/utils/src/math/levenshtein_distance.rs b/utils/src/math/levenshtein_distance.rs new file mode 100644 index 0000000..98caa20 --- /dev/null +++ b/utils/src/math/levenshtein_distance.rs @@ -0,0 +1,38 @@ +use std::cmp::min; + +pub fn levenshtein_distance(a: &str, b: &str) -> usize { + let a_len = a.chars().count(); + let b_len = b.chars().count(); + + if a_len == 0 { + return b_len; + } + if b_len == 0 { + return a_len; + } + + let mut prev_row: Vec = (0..=b_len).collect(); + let mut curr_row = vec![0; b_len + 1]; + + let mut a_chars = a.chars(); + + for i in 1..=a_len { + let a_char = a_chars.next().unwrap(); + curr_row[0] = i; + + let mut b_chars = b.chars(); + for j in 1..=b_len { + let b_char = b_chars.next().unwrap(); + + let cost = if a_char == b_char { 0 } else { 1 }; + curr_row[j] = min( + prev_row[j] + 1, + min(curr_row[j - 1] + 1, prev_row[j - 1] + cost), + ); + } + + std::mem::swap(&mut prev_row, &mut curr_row); + } + + prev_row[b_len] +} -- cgit