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$.
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.
Comments
Post a Comment