JuniorCodeCommonNot answered yet
One-edit-apart check between two strings
Return true if string a can be turned into string b with at most one edit: one insertion, one deletion, or one character replacement.
Requirements:
- O(n) time, O(1) extra space — no edit-distance matrix.
bool oneEditApart(const std::string& a, const std::string& b) {
// your code here
}Write the implementation.
If the lengths differ by more than 1, return false. If equal, count character mismatches and accept at most one. If they differ by 1, scan with two pointers allowing exactly one skip in the longer string; any second mismatch fails. One pass, O(n) time, O(1) space.
- ✗Treating the equal-length and differ-by-one cases identically, mishandling the insert/delete skip
- ✗Forgetting to reject immediately when lengths differ by more than one
- ✗Allowing a second mismatch after the single permitted edit
- →Why does a length difference greater than one let you return early?
- →How does the two-pointer skip model an insertion versus a deletion?
Contents
Task
Return true if a becomes b with at most one edit, in O(n) time and O(1) space.
Solution
bool oneEditApart(const std::string& a, const std::string& b) {
int la = a.size(), lb = b.size();
if (std::abs(la - lb) > 1) return false;
if (la == lb) { // replace case
int diff = 0;
for (int i = 0; i < la; ++i) if (a[i] != b[i] && ++diff > 1) return false;
return true;
}
const std::string& s = la < lb ? a : b; // shorter
const std::string& l = la < lb ? b : a; // longer
int i = 0, j = 0; bool skipped = false;
while (i < static_cast<int>(s.size())) {
if (s[i] != l[j]) {
if (skipped) return false; // a second skip is not allowed
skipped = true; ++j; // skip in the longer string
} else { ++i; ++j; }
}
return true;
}Key points
- A length difference > 1 is an immediate reject.
- Equal lengths is the replace case (count mismatches, allow one).
- Difference of 1 is insert/delete: one skip in the longer string, a second is forbidden.
Contents
