Going the Distance
summary
Starts with a naive character loop, then a recursive Levenshtein that returns 1,647 comparisons for Saturday→Sunday, then an optimized matrix version that drops to 48 iterations and yields the correct distance of 3. Shows runnable Ruby scripts on GitHub and uses Heroku for deployment, explains caching of substring costs, and mentions integrating a misspelling helper into Rails as PR 15497 that recommends generators when a name is typed wrong.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 3:05Rails contributions focus
- 5:14Algorithms are beautiful
- 6:41Hamming distance limits
- 9:57Levenshtein distance intro
- 13:35Recursive Levenshtein implementation
- 15:41Matrix-based Levenshtein optimization
- 21:38Rails generators application
- 25:05Google spellchecking algorithms
- 27:17Other distance algorithms
- 27:58Algorithm learning resources
- 29:21Value of deep algorithm understanding
