Verify only 1 edit action required to string in Javascript

This problem is a common interview question. The problem is to check if two strings are one (or zero) edits away. An edit can be either:

• an insertion,
• a removal,
• or a replacement of a single character.

Code sample solution

Here is a simple and efficient JavaScript function to solve this problem:

function isOneEditAway(s1, s2) {
    if (Math.abs(s1.length - s2.length) > 1) {
        return false;  // More than one insert/remove needed
    }

    let i = 0, j = 0, edits = 0;

    while (i < s1.length && j < s2.length) {
        if (s1[i] !== s2[j]) {
            if (edits === 1) {
                return false;  // More than one edit needed
            }

            if (s1.length > s2.length) {
                i++;  // Possible remove in s1
            } else if (s1.length < s2.length) {
                j++;  // Possible insert in s1
            } else {
                i++;  // Possible replace in s1
                j++;
            }

            edits++;
        } else {
            i++;
            j++;
        }
    }

    return true;
}

console.log(isOneEditAway('pale', 'ple'));  // Should print: true
console.log(isOneEditAway('pales', 'pale'));  // Should print: true
console.log(isOneEditAway('pale', 'bale'));  // Should print: true
console.log(isOneEditAway('pale', 'bake'));  // Should print: false

Explanation

In this function, isOneEditAway, we first check if the lengths of the strings differ by more than 1. If so, we immediately return false, as more than one insert/remove would be needed.

We then iterate over both strings simultaneously. If we find a pair of characters that don’t match, we check if we’ve already found a previous mismatch (if edits is 1). If so, we return false, as more than one edit would be needed.

If it’s the first mismatch (edits is 0), we increment i and/or j depending on the lengths of the strings. This is because a mismatch could mean a possible remove in s1 (if s1 is longer), a possible insert in s1 (if s1 is shorter), or a possible replacement in s1 (if s1 and s2 are the same length).

Finally, if we’ve made it through both strings without returning false, we return true, meaning the strings are one edit away (or zero edits away, i.e., the same).

Info time complexity

This function has a time complexity of O(n), where n is the length of the strings. We iterate over each string once, and all operations within the loop can be done in constant time. Therefore, this function is very efficient.