> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/strings/32.-one-edit-distance.md).

# 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)

```cpp
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)**