Finding editing distance

Problem 

 Given two strings, return boolean True/False, if they are only one edit apart.

  Edit can be insert/delete/update of only one character in the string.

  

  Eg.:

  

  True:

  xyz, xz

  xyz, xyk

  xy, xyz

  False:

  xyz, xyz

  xyz, xzy

  x, xyz

 In comparing two strings there are two cases to be considered.

Answer

Case 1: two string are in the same length
 In this case, we can compare each letter in the strings sequentially and record any mismatches during the comparison. The number of matching counts should be $Length(input) - 1$.

Case 2: two string are not in the same length (UPDATE 2022-06-14: removed the subcase)

In this case, we just examine the letters sequentially. When a mismatch happens, we record the mismatch and only increase the next position of the longer string leaving the position of the short string as it is. It is to skip the mismatching letter in the longer string to find the matching one coming next.

The overall running time of this algorithm is O(N).

Here is the complete code in C++.


Practice statistics:

Planning:    8.47 mins
Coding :     8.55 mins
Validation: 8.11 mins

Note: Made a couple of typos found by IDE and made a critical mistake in logic.

UPDATE(2022-06-14): Solve the problem again and found that the original algorithm has the necessary sub-case. Simplified the algorithm into two cases.

8:00: for algorithm

12:00: coding

08:42: for fixing the silly but critical mistake.