1 files changed, 38 insertions, 0 deletions
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<usize> = (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]
+}