Given two strings, write a function to check if they are one edit (or zero edits) away

by

QUESTION:

One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

EXAMPLE:
pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bae -> false

SOLUTION:

  • There is a “brute force” algorithm to do this. We could check all possible strings that are one edit away by testing the removal of each character (and comparing), testing the replacement of each character (and comparing), and then testing the insertion of each possible character (and comparing).
  • That would be too slow, so let’s not bother with implementing it.
  • This is one of those problems where it’s helpful to think about the “meaning” of each of these operations.
  • What does it mean for two strings to be one insertion, replacement, or removal away from each other?
    • Replacement: Consider two strings, such as bale and pale, that are one replacement away. Yes, that does mean that you could replace a character in bale to make pale. But more precisely, it means that they are different only in one place.
    • Insertion: The strings apple and aple are one insertion away. This means that if you compared the strings, they would be identical-except for a shift at some point in the strings.
    • Removal: The strings apple and aple are also one removal away, since removal is just the inverse of insertion.
  • We can go ahead and implement this algorithm now. We’ll merge the insertion and removal check into one step, and check the replacement step separately.

Observe that you don’t need to check the strings for insertion, removal, and replacement edits. The lengths of the strings will indicate which of these you need to check.

boolean oneEditAway(String first, String second) {
if (first.length()== second.length()) {
return oneEditReplace(first, second);
} else if (first.length()+ 1 == second.length()) {
return oneEditinsert(first, second);
} else if (first.length() - 1 == second.length()) {
return oneEditinsert(second, first);
}
return false;
 }
 
boolean oneEditReplace(String sl, String s2) {
boolean foundDifference = false;
for (int i= 0; i < sl.length(); i++) {
if (sl.charAt(i) != s2.charAt(i)) {
if (foundDifference) {
return false; 
}
foundDifference = true;
}
}
return true;
}

/* Check if you can insert a character into sl to make s2. */
 boolean oneEditinsert(String sl, String s2) {
int indexl = 0;
int index2 = 0;
while (index2 < s2.length() && indexl < sl.length()) {
if (sl.charAt(indexl) != s2.charAt(index2)) {
if (indexl != index2) {
return false;
}
index2++;
} else {
indexl++;
index2++;
}
}
return true;
}

This algorithm (and almost any reasonable algorithm) takes O ( n) time, where n is the length of the shorter string.

Why is the runtime dictated by the shorter string instead of the longer string? If the strings are the same length (plus or minus one character), then it doesn’t matter whether we use the longer stringor the shorter string to define the runtime. If the strings are very different lengths, then the algorithm will terminate in 0( 1) time. One really, really long string therefore won’t significantly extend the runtime. It increases the runtime only if both strings are long.

We might notice that the code for one Edit Replace is very similar to that for one Edit insert. We can merge them into one method.

  • To do this, observe that both methods follow similar logic: compare each character and ensure that the strings are only different by one. The methods vary in how they handle that difference.
  • Method one Edit Replace does nothing other than flag the difference, whereas one Edit inserts increments the pointer to the longer string. We can handle both of these in the same method.
boolean oneEditAway(String first, String second) {
/* Length checks. */
if (Math.abs(first.length() - second.length()) > 1) {
return false;
}

/* Get shorter and longer string.*/
String sl first.length()< second.length() ? first : second;
String s2 =first.length()< second.length() ? second : first;
int indexl = 0;
int index2 = 0;
boolean foundDifference = false;
while (index2 < s2.length() && indexl < sl.length()) {
1if (sl.charAt(indexl) != s2.charAt(index2)) {
/* Ensure that this is the first difference found.*/
if (foundDifference) return false;
foundDifference = true;
if (sl.length() == s2.length()) {//On replace, move shorter pointer
indexl++;
}
} else {
indexl++; // If matching, move shorter pointer
}
index2++; // Always move pointer for longer string
}
return true;
}
  • Some people might argue the first approach is better, as it is clearer and easier to follow.
  • Others, however, will argue that the second approach is better, since it’s more compact and doesn’t duplicate code (which can facilitate maintainability).

You don’t necessarily need to “pick a side:’You can discuss the tradeoffs with your interviewer.

Leave a Comment