1pub fn is_near(a: &str, b: &str) -> bool {
2 is_contained_near(a, b) || levenshtein(a, b) <= 2
3}
4
5fn is_contained_near(a: &str, b: &str) -> bool {
6 let shorter = a.len().min(b.len());
7 let longer = a.len().max(b.len());
8 shorter * 2 >= longer && (a.contains(b) || b.contains(a))
9}
10
11fn levenshtein(a: &str, b: &str) -> usize {
12 let mut costs: Vec<usize> = (0..=b.len()).collect();
13 for (i, ca) in a.chars().enumerate() {
14 let mut prev = i;
15 costs[0] = i + 1;
16 for (j, cb) in b.chars().enumerate() {
17 let old = costs[j + 1];
18 costs[j + 1] = if ca == cb {
19 prev
20 } else {
21 1 + prev.min(costs[j]).min(costs[j + 1])
22 };
23 prev = old;
24 }
25 }
26 costs[b.len()]
27}