edit distance
The minimum number of single-character insertions, deletions and substitutions needed to turn one string into another.
In more detail
Turning "kitten" into "sitting" takes three edits. Dynamic programming fills a table where each cell takes the cheapest of the three moves from its neighbours, in O(m × n). Spell checkers and fuzzy search use it to find near matches.
Examples
examp1e.com edits: 1example-invoices.com edits: 9The course computes edit scripts with Python's difflib.SequenceMatcher.Related terms
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- longest common subsequence — The longest sequence of characters that appears, in order but not necessarily side by side, in both of two strings.
- tabulation — Bottom-up dynamic programming: filling a table of subproblem answers in order from the base cases up, so each entry's inputs are ready before it.
- typosquatting — Registering a name that differs from a popular one by a small typing mistake, such as a lookalike domain or package name, to catch people who mistype it.
- lookalike domain — A domain name made to resemble a trusted one, such as evilexample.com next to example.com, to trick people or filters.
- combosquatting — Registering a domain that contains a real brand name plus extra words, such as the brand followed by a word like invoices or login.
Taught in
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Social Engineering, Phishing & Human Defense — Cybersecurity Fundamentals, GRC & Cryptography
- Dependency Risk And Typosquatting — Application Security & Threat Modeling for Engineers