Algorithm dossier

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

Why this snippet is Longest Common Subsequence

Why LCS. Two-string DP on a 2D grid. The recurrence at f[i][j] is "if the last chars match, extend the diagonal; otherwise inherit the better of dropping a char from s (above) or from t (left)." Confusable with. Edit distance — same grid shape, but edit distance *adds* on mismatch (cost of an edit), while LCS *inherits* the better neighbour. The recurrence body is the difference.

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.