32. One Edit Distance

Given two strings s0 and s1 determine whether they are one or zero edit distance away. An edit can be described as deleting a character, adding a character, or replacing a character with another character.

Constraints

• n ≤ 100,000 where n is the length of s0.

• m ≤ 100,000 where m is the length of s1.

Example 1

s0 = "quicksort"
s1 = "quicksort"

Output
true

Explanation

This has the edit distance of 0, since they are the same string.

Example 2

s0 = "mergesort"
s1 = "mergesorts"

Output
true

Explanation

This has the edit distance 1, since s was added to the second string.

Example 3

s0 = "mergeport"
s1 = "mergesorts"

Output
false

Explanation

This has edit distance of 2.

Solution: (Without DP)

bool solve(string s0, string s1) {
    int n = s0.length();
    int m = s1.length();

    int dif = abs(n - m);

    if (dif > 1) {
        return false;
    }

    int i = 0, j = 0;
    int count = 0;

    while (i < n && j < m) {
        if (s0[i] == s1[j]) {
            i++;
            j++;
        } else {
            if (n > m) {
                i++;
            } else if (m > n) {
                j++;
            } else {
                i++;
                j++;
            }

            count++;
        }

        if (count > 1) {
            return false;
        }
    }

    return true;
}

Time Complexity: O(n)