Function levenshtein_diff::distance::levenshtein_memoization

pub fn levenshtein_memoization<T, U>(i1: U, i2: U) -> (usize, DistanceMatrix) where
    T: PartialEq,
    U: AsRef<[T]>, 

Returns the Levenshtein distance and the distance matrix between source and target using dynamic programming with memoization.

This implementation has a time complexity of O(n^2) and a space complexity of O(n^2).

Arguments

• source - The source sequence
• target - The target sequence

Examples

use levenshtein_diff as levenshtein;

let s1 = "SATURDAY";
let s2 = "SUNDAY";
let expected_leven = 3;
let (leven_naive, _) = levenshtein::levenshtein_memoization(s1, s2);
assert_eq!(leven_naive, expected_leven);