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.

image

Solutions

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?

1. 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.

2. 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.

3. 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.

class MyClass
{

    public bool OneEditAway(string first, string second)
    {

        if (first is not null && second is not null)
        {
            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;

    }

    private bool OneEditReplace(string first, string second)
    {
        bool diffFound = false;
        for (int i = 0; i < first.Length; i++)
        {
            if (first[i] != second[i])
            {
                if (diffFound)
                {
                    return false;
                }
                diffFound = true;
            }

        }
        return true;
    }

    private bool OneEditInsert(string small, string large)
    {
        int index1 = 0;
        int index2 = 0;
        while (index1 < small.Length && index2 < large.Length)
        {
            if (small[index1] != large[index2])
            {
                if (index1 != index2)
                {
                    return false;
                }
                index2++;
            }
            else
            {
                index1++;
                index2++;
            }
        }
        return true;

    }
}

Time complexity: O(n)

Space complexity: O(1)