const FURTHEST: usize = 2;
pub(crate) fn nearest<'a, I>(word: &str, choices: I) -> Option<&'a str>
where
I: IntoIterator<Item = &'a str>,
{
let scored = choices.into_iter().map(|c| (distance(word, c), c));
let close = scored.filter(|(d, _)| *d <= FURTHEST && *d > 0);
close.min_by_key(|(d, _)| *d).map(|(_, choice)| choice)
}
fn distance(a: &str, b: &str) -> usize {
let b: Vec<char> = b.chars().collect();
let mut row: Vec<usize> = (0..=b.len()).collect();
for (i, ca) in a.chars().enumerate() {
row = next_row(&row, ca, &b, i.saturating_add(1));
}
row.last().copied().unwrap_or_default()
}
fn next_row(row: &[usize], ca: char, b: &[char], first: usize) -> Vec<usize> {
let mut next = vec![first];
let mut diagonal = row.first().copied().unwrap_or_default();
for (j, cb) in b.iter().enumerate() {
let up = row.get(j.saturating_add(1)).copied().unwrap_or(usize::MAX);
let left = next.last().copied().unwrap_or(usize::MAX);
let swap = diagonal.saturating_add(usize::from(ca != *cb));
next.push(swap.min(up.saturating_add(1)).min(left.saturating_add(1)));
diagonal = up;
}
next
}
#[cfg(test)]
mod tests {
use super::{distance, nearest};
#[test]
fn distance_counts_single_char_edits() {
assert_eq!(distance("chek", "check"), 1);
assert_eq!(distance("check", "check"), 0);
assert_eq!(distance("", "abc"), 3);
assert_eq!(distance("kitten", "sitting"), 3);
}
#[test]
fn a_suggestion_is_close_or_absent() {
let verbs = ["check", "explain", "sets", "fix", "stats"];
assert_eq!(nearest("chek", verbs), Some("check"));
assert_eq!(nearest("stat", verbs), Some("stats"));
assert_eq!(nearest("deploy", verbs), None);
assert_eq!(nearest("check", verbs), None);
}
}