Algorithms and Data Structures · Middle · Question 46 of 75
What does the Levenshtein (edit) distance measure?
- 1The difference in length between the two strings
- 2The number of positions where two equal-length strings differ
- ✓Correct answer: Minimum inserts, deletes and substitutions to turn one into the other
Explanation
It's computed with an O(n × m) DP table and powers spell checkers and "did you mean...?" suggestions. Counting differing positions in equal-length strings is the Hamming distance.