Edit Distance

The edit distance between two strings is the minimum number of single-character edits needed to turn one into the other, where each edit is an insert, a delete, or a replace and every edit costs 1. This is the classic Levenshtein distance (LeetCode 72): given word1 and word2, return the fewest operations that transform word1 into word2. It is the measure behind spell-checkers, fuzzy search, and DNA-sequence comparison — anywhere you need to score how far apart two strings are. See Levenshtein distance for background.

Signature

editDistance(word1, word2)   // two strings -> minimum edit count (a number)

Examples

editDistance('horse', 'ros');    // 3  (replace h→r, delete r, delete e)
editDistance('ab', 'abc');       // 1  (insert one character)
editDistance('', 'abc');         // 3  (insert every character)
editDistance('abcde', 'abcde');  // 0  (already identical)

Notes

• Three operations — insert a character, delete a character, or replace one character with another. Each costs exactly 1; matching a character that is already correct costs nothing.
• Symmetric — editDistance(a, b) always equals editDistance(b, a), because an insert in one direction is a delete in the other.
• Empty string — the distance from '' to any string is that string's length (you insert every character), and the same the other way.
• Result — always a non-negative integer; it is 0 only when the two strings are already identical. Comparison is case-sensitive, and you should build the function yourself without a library.