rust 27 lines · 6 steps

Levenshtein distance with two rows in Rust

Computes edit distance between two strings using rolling rows instead of a full matrix.

Explained by highlit
Intermediate dynamic-programming edit-distance space-optimization strings
1pub fn levenshtein(a: &str, b: &str) -> usize {
2 let a: Vec<char> = a.chars().collect();
3 let b: Vec<char> = b.chars().collect();
4 
5 if a.is_empty() {
6 return b.len();
7 }
8 if b.is_empty() {
9 return a.len();
10 }
11 
12 let mut prev: Vec<usize> = (0..=b.len()).collect();
13 let mut curr = vec![0usize; b.len() + 1];
14 
15 for (i, &ca) in a.iter().enumerate() {
16 curr[0] = i + 1;
17 for (j, &cb) in b.iter().enumerate() {
18 let cost = if ca == cb { 0 } else { 1 };
19 curr[j + 1] = (prev[j + 1] + 1)
20 .min(curr[j] + 1)
21 .min(prev[j] + cost);
22 }
23 std::mem::swap(&mut prev, &mut curr);
24 }
25 
26 prev[b.len()]
27}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Collecting to Vec<char> lets you index by character, avoiding UTF-8 byte-boundary pitfalls.
  2. 2Edit distance only needs the previous row, so two rolling arrays replace the full O(n*m) matrix.
  3. 3Each cell is the cheapest of deletion, insertion, or substitution from its neighbors.

Related explainers

rust 
use axum::{extract::{Path, State}, http::StatusCode, Json};
use dashmap::DashMap;
use serde::Serialize;
use std::sync::Arc;

Request coalescing in an Axum handler

caching concurrency request-coalescing
Advanced 8 steps
rust 
use std::net::Ipv4Addr;
use std::str::FromStr;
 
#[derive(Debug, Clone, Copy)]

Parsing and matching IPv4 CIDR ranges in Rust

bitwise-operations parsing error-handling
Intermediate 8 steps
rust 
use std::sync::OnceLock;
 
static CRC_TABLE: OnceLock<[u32; 256]> = OnceLock::new();
 

Table-driven CRC32 with lazy init in Rust

checksums lazy-initialization lookup-tables
Intermediate 8 steps
rust 
use axum::{
    body::Body,
    extract::Path,
    http::{header, HeaderMap, HeaderValue, StatusCode},

HTTP range requests for video streaming in Axum

http-range-requests streaming async-io
Advanced 8 steps
rust 
use std::sync::mpsc;
use std::thread;
use std::time::Duration;
 

Running work with a timeout in Rust

concurrency channels timeout
Intermediate 7 steps
rust 
use axum::{extract::State, response::IntoResponse, Json};
use serde::{Deserialize, Serialize};
use serde_json::{json, Value};
use std::sync::Arc;

Building a JSON-RPC 2.0 handler in Axum

json-rpc serde request-dispatch
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

Levenshtein distance with two rows in Rust — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code