jonnifyelixir
F4 / F4.11 / problems

F4.11 · part 3 of 3 · typo-tolerant search

Classic DP problems

When a learner mistypes a course name in the search box, the Portal still wants to find it. The measure is edit distance: the fewest single-character inserts, deletes, or substitutions that turn one string into another. It is the textbook two-dimensional dynamic program — a cell for every pair of prefixes, each built from the three cells above and to its left — and it powers the “did you mean” suggestion under the search bar.

A misspelled query against the catalog entry elixir. Pick a query and watch the table fill; the bottom-right cell is the distance.

Fill the grid Advanced: cost, space, and scale

Fill the grid

Rows are the typed query, columns the target elixir; dp[i][j] is the distance between their first i and j characters. Each cell is the cheapest of a delete, an insert, or a substitute — free when the two characters match. Pick a query.

Typed query · select one · target “elixir”

query: elixr target: elixir edit distance: 1 did you mean “elixir”? 

      

      
query: elixr

      
edit distance: 1

    

    
The whole table is solved cell by cell from the empty-prefix edges inward, and the single
      bottom-right number is the answer. Below a threshold of two edits, the Portal offers the match as a suggestion.

  


  

    
Advanced: cost, space, and scale

    

      
Edit distance has the two DP hallmarks. Optimal substructure: the best alignment of two strings is built from
        the best alignment of their prefixes, which is the recurrence each cell encodes. Overlapping subproblems: a
        prefix pair is reused by every longer pair that extends it, so the table fills each once. The work is
        O(m × n) for strings of length m and n — one pass over the
        grid — and the same shape solves longest-common-subsequence and sequence alignment by changing only the
        per-cell rule.

      
Two practical notes. Only the previous row is needed to compute the next, so the full grid can collapse to
        O(min(m, n)) space when you want only the number; the full grid is kept solely to trace
        the actual edits back. And comparing a query against every catalog title is fine for a small catalog but is
        linear in its size; at scale the Portal would index titles — a BK-tree or trigram index — and
        compute edit distance only against the near matches, rather than the whole list.

    

    
# edit distance, row by row; suggest when it is small
def distance(a, b) do
  a = String.graphemes(a)
  b = String.graphemes(b)
  row0 = Enum.to_list(0..length(b))

  Enum.reduce(Enum.with_index(a, 1), row0, fn {ca, i}, prev ->
    Enum.scan(Enum.with_index(b, 1), i, fn {cb, j}, left ->
      cost = if ca == cb, do: 0, else: 1
      min(min(left + 1, Enum.at(prev, j) + 1), Enum.at(prev, j - 1) + cost)
    end)
  end)
  |> List.last()
end

    

      

        
two strings

        
A misspelled query and a catalog title.

      

      
      

        
an alignment cost

        
One grid, filled once; the corner cell is the fewest edits between them.

      

    

    
That completes F4.11: overlapping subproblems solved once, top-down with a cache, bottom-up in a
      table, and across a two-dimensional grid. Next module: F4.12 — Lab: build a branded CHAMP
      store, which closes the chapter by assembling the pieces into a working store.

  


  

    
References

    
Primary sources for this lesson, and where it connects in the course.

    

      
Sources

      
      
Related in this course