This content originally appeared on DEV Community and was authored by Wing-Kam WONG
https://binarysearch.com/problems/One-Edit-Distance
Problem
Given two strings s0 and s1 determine whether they are one or zero edit distance away. An edit can be described as deleting a character, adding a character, or replacing a character with another character.
Constraints
n ≤ 100,000 where n is the length of s0.
m ≤ 100,000 where m is the length of s1.
Solution
Find the first index i that s0[i] is not equal to s1[i]
Based on the length of s0 and s1, compare the rest of the sub string are same or not.
bool solve(string s0, string s1) {
int m = s0.size(), n = s1.size();
for (int i = 0; i < min(m, n); i++) {
if (s0[i] != s1[i]) {
if (m == n)
return s0.substr(i + 1) == s1.substr(i + 1);
else if (m < n)
return s0.substr(i) == s1.substr(i + 1);
else
return s0.substr(i + 1) == s1.substr(i);
}
}
return abs(m - n) <= 1;
}
This content originally appeared on DEV Community and was authored by Wing-Kam WONG
Wing-Kam WONG | Sciencx (2021-10-02T02:32:47+00:00) BinarySearch – One Edit Distance. Retrieved from https://www.scien.cx/2021/10/02/binarysearch-one-edit-distance/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.