01.05. One Away

Description

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


Input:

first = "pale"

second = "ple"

Output: True

Example 2:


Input:

first = "pales"

second = "pal"

Output: False

Solutions

Solution 1: Case Discussion + Two Pointers

We denote the lengths of strings $first$ and $second$ as $m$ and $n$, respectively, where $m \geq n$.

Next, we discuss different cases:

When $m - n > 1$, $first$ and $second$ cannot be obtained through a single edit, so we return false.
When $m = n$, $first$ and $second$ can only be obtained through a single edit if and only if exactly one character is different.
When $m - n = 1$, $first$ and $second$ can only be obtained through a single edit if and only if $second$ is obtained by deleting one character from $first$. We can use two pointers to implement this.

The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptRustSwift

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        m, n = len(first), len(second)
        if m < n:
            return self.oneEditAway(second, first)
        if m - n > 1:
            return False
        if m == n:
            return sum(a != b for a, b in zip(first, second)) < 2
        i = j = cnt = 0
        while i < m:
            if j == n or (j < n and first[i] != second[j]):
                cnt += 1
            else:
                j += 1
            i += 1
        return cnt < 2