Algorithm dossier

  • Category: DP
  • Worst-case complexity: O(n²)
  • Approach: DP
  • Data structure: Array
  • First formalised: 1960s

Why this snippet is Edit Distance (Levenshtein)

Why edit distance. Three-way min on mismatch is the signature: cost of a deletion (f[i-1][j]), an insertion (f[i][j-1]), or a substitution (f[i-1][j-1]), plus 1. On match, inherit the diagonal for free. Why not LCS. LCS does max (and never adds 1 on mismatch — it just inherits the better neighbour). Both are 2D string DPs; the recurrence body is the tell.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.