One Time Editing#

There are three types of editing operations for strings: inserting a character, deleting a character, or replacing a character. Given two strings, write a function to determine whether they need only one time (or zero times) editing.

Example#

Solution#

/**
 * @param {string} first
 * @param {string} second
 * @return {boolean}
 */
var oneEditAway = function(first, second) {
    if(first === second) return true;
    var firstLen = first.length;
    var secondLen = second.length;
    if(Math.abs(firstLen - secondLen) > 1) return false;
    var firstStart = 0;
    var secondStart = 0;
    var firstEnd = firstLen-1;
    var secondEnd = secondLen-1;
    while(firstStart < firstLen && secondStart < secondLen && first[firstStart] === second[secondStart]){
        ++firstStart;
        ++secondStart;
    }
    while(firstEnd >= 0 && secondEnd >= 0 && first[firstEnd] === second[secondEnd]){
        --firstEnd;
        --secondEnd;
    }
    return (firstEnd - firstStart < 1) && (secondEnd - secondStart < 1);
};

Idea#

Use a two-pointer approach to traverse the two strings from the beginning to the first different position and from the end to the first different position, then compare the differences, that is, align the ends of the strings according to the differences, and then compare the differences between the positions. First, determine if the strings are the same, if so, return true directly. Then get the lengths of the two strings for comparison. If the difference in lengths is greater than 1, return false directly. Then for the two strings, define two pointers and traverse the strings in both forward and backward directions, positioning the pointers to the location of different characters. Finally, compare the difference between the pointer positions.

Daily Question#

Reference#