edit distance

Edit distance measures how different two strings are by counting the fewest single-character edits needed to turn one into the other. The allowed edits are inserting a character, deleting a character, and substituting one character for another, each costing one. So the edit distance from 'kitten' to 'sitting' is 3: substitute k->s, substitute e->i, and insert a g. This is the number behind spell-checkers ('did you mean...?'), fuzzy search, and DNA comparison, because it captures intuitively how close two sequences are.

The DP compares the strings prefix by prefix. Let dp[i][j] be the edit distance between the first i characters of A and the first j characters of B. If the current last characters match (A[i] = B[j]), no edit is needed for them, so dp[i][j] = dp[i-1][j-1]. If they differ, you pay 1 for one of three edits and take the cheapest: dp[i][j] = 1 + min( dp[i-1][j] for deleting A[i], dp[i][j-1] for inserting B[j], dp[i-1][j-1] for substituting ). The base cases say converting to or from the empty string costs one edit per remaining character: dp[i][0] = i (delete all of A's first i) and dp[0][j] = j (insert all of B's first j). Filling the table top-to-bottom, left-to-right, takes O(mn) time and O(mn) space, reducible to O(min(m, n)) space with a rolling two-row array if you only need the number.

Edit distance is a close cousin of the longest common subsequence — both compare prefixes and look at the last characters — but it minimizes a cost of changes rather than maximizing a length of agreement, which is a useful pair to hold side by side. Two honest notes. First, the answer is a genuine distance in the mathematical sense (it is symmetric and obeys the triangle inequality), which is why it behaves well as a similarity score. Second, this basic version charges 1 per edit; variants with different costs (a substitution costing 2, or weights per character pair as in biological alignment) just change the numbers added in the transition, but the same DP shape carries over.