// 1056: Edit Distance (Levenshtein) — 2D DP Table
use std::collections::HashMap;
// Approach 1: 2D DP table
fn edit_distance(s1: &str, s2: &str) -> usize {
let a: Vec<char> = s1.chars().collect();
let b: Vec<char> = s2.chars().collect();
let (m, n) = (a.len(), b.len());
let mut dp = vec![vec![0; n + 1]; m + 1];
for i in 0..=m { dp[i][0] = i; }
for j in 0..=n { dp[0][j] = j; }
for i in 1..=m {
for j in 1..=n {
dp[i][j] = if a[i - 1] == b[j - 1] {
dp[i - 1][j - 1]
} else {
1 + dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1])
};
}
}
dp[m][n]
}
// Approach 2: Space-optimized with two rows
fn edit_distance_opt(s1: &str, s2: &str) -> usize {
let a: Vec<char> = s1.chars().collect();
let b: Vec<char> = s2.chars().collect();
let (m, n) = (a.len(), b.len());
let mut prev: Vec<usize> = (0..=n).collect();
let mut curr = vec![0; n + 1];
for i in 1..=m {
curr[0] = i;
for j in 1..=n {
curr[j] = if a[i - 1] == b[j - 1] {
prev[j - 1]
} else {
1 + prev[j].min(curr[j - 1]).min(prev[j - 1])
};
}
std::mem::swap(&mut prev, &mut curr);
}
prev[n]
}
// Approach 3: Recursive with memoization
fn edit_distance_memo(s1: &str, s2: &str) -> usize {
let a: Vec<char> = s1.chars().collect();
let b: Vec<char> = s2.chars().collect();
fn solve(i: usize, j: usize, a: &[char], b: &[char], cache: &mut HashMap<(usize, usize), usize>) -> usize {
if i == 0 { return j; }
if j == 0 { return i; }
if let Some(&v) = cache.get(&(i, j)) { return v; }
let v = if a[i - 1] == b[j - 1] {
solve(i - 1, j - 1, a, b, cache)
} else {
1 + solve(i - 1, j, a, b, cache)
.min(solve(i, j - 1, a, b, cache))
.min(solve(i - 1, j - 1, a, b, cache))
};
cache.insert((i, j), v);
v
}
let mut cache = HashMap::new();
solve(a.len(), b.len(), &a, &b, &mut cache)
}
fn main() {
println!("edit_distance(\"kitten\", \"sitting\") = {}", edit_distance("kitten", "sitting"));
println!("edit_distance(\"saturday\", \"sunday\") = {}", edit_distance("saturday", "sunday"));
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_edit_distance() {
assert_eq!(edit_distance("kitten", "sitting"), 3);
assert_eq!(edit_distance("saturday", "sunday"), 3);
assert_eq!(edit_distance("", "abc"), 3);
assert_eq!(edit_distance("abc", "abc"), 0);
}
#[test]
fn test_edit_distance_opt() {
assert_eq!(edit_distance_opt("kitten", "sitting"), 3);
assert_eq!(edit_distance_opt("saturday", "sunday"), 3);
}
#[test]
fn test_edit_distance_memo() {
assert_eq!(edit_distance_memo("kitten", "sitting"), 3);
assert_eq!(edit_distance_memo("saturday", "sunday"), 3);
}
}
(* 1056: Edit Distance (Levenshtein) — 2D DP Table *)
(* Approach 1: 2D DP table *)
let edit_distance s1 s2 =
let m = String.length s1 and n = String.length s2 in
let dp = Array.init (m + 1) (fun i ->
Array.init (n + 1) (fun j ->
if i = 0 then j else if j = 0 then i else 0
)
) in
for i = 1 to m do
for j = 1 to n do
if s1.[i - 1] = s2.[j - 1] then
dp.(i).(j) <- dp.(i - 1).(j - 1)
else
dp.(i).(j) <- 1 + min (min dp.(i - 1).(j) dp.(i).(j - 1)) dp.(i - 1).(j - 1)
done
done;
dp.(m).(n)
(* Approach 2: Space-optimized with two rows *)
let edit_distance_opt s1 s2 =
let m = String.length s1 and n = String.length s2 in
let prev = Array.init (n + 1) Fun.id in
let curr = Array.make (n + 1) 0 in
for i = 1 to m do
curr.(0) <- i;
for j = 1 to n do
if s1.[i - 1] = s2.[j - 1] then
curr.(j) <- prev.(j - 1)
else
curr.(j) <- 1 + min (min prev.(j) curr.(j - 1)) prev.(j - 1)
done;
Array.blit curr 0 prev 0 (n + 1)
done;
prev.(n)
(* Approach 3: Recursive with memoization *)
let edit_distance_memo s1 s2 =
let cache = Hashtbl.create 128 in
let rec solve i j =
if i = 0 then j
else if j = 0 then i
else
match Hashtbl.find_opt cache (i, j) with
| Some v -> v
| None ->
let v =
if s1.[i - 1] = s2.[j - 1] then solve (i - 1) (j - 1)
else 1 + min (min (solve (i - 1) j) (solve i (j - 1))) (solve (i - 1) (j - 1))
in
Hashtbl.add cache (i, j) v;
v
in
solve (String.length s1) (String.length s2)
let () =
assert (edit_distance "kitten" "sitting" = 3);
assert (edit_distance "saturday" "sunday" = 3);
assert (edit_distance "" "abc" = 3);
assert (edit_distance "abc" "" = 3);
assert (edit_distance "abc" "abc" = 0);
assert (edit_distance_opt "kitten" "sitting" = 3);
assert (edit_distance_opt "saturday" "sunday" = 3);
assert (edit_distance_memo "kitten" "sitting" = 3);
assert (edit_distance_memo "saturday" "sunday" = 3);
Printf.printf "✓ All tests passed\n"