Algorithms and Data Structures · Senior · Question 67 of 75
How do you check whether two words are one edit apart in O(n)?
- 1Compute the full Levenshtein table and check for 1
- 2Sort both words and compare the sorted results
- ✓Correct answer: Two pointers, allowing a single skip or mismatch
Explanation
If lengths differ by more than one, the answer is no. Otherwise move pointers together and, at the first mismatch, skip a character in the longer word (or both for equal length). The full DP is O(n × m).