One Edit Distance

Medium Arrays & Hashing Two Pointer Original on LeetCode

Reported atStripe

One Edit Distance is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (single pass to the first mismatch), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every single edit) up.

Problem

Given two strings s and t, decide whether they are exactly one edit apart. A single edit is one of:

  • inserting one character anywhere in s,
  • deleting one character from s,
  • replacing one character of s with a different character.

Return true if exactly one such edit turns s into t, and false otherwise. Two equal strings are zero edits apart, so they return false.

Examples

Example 1

Input
s = "plane", t = "planet"
Output
true
Why
Appending t to the end of plane gives planet, which is a single insertion.

Example 2

Input
s = "cost", t = "cast"
Output
true
Why
Only position 1 differs, so one replacement (o -> a) is enough.

Example 3

Input
s = "moon", t = "moon"
Output
false
Why
The strings are already equal; they are zero edits apart, not exactly one.

Constraints

  • 0 <= s.length, t.length <= 10^4
  • s and t consist of lowercase letters, uppercase letters and digits.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every single edit)O(n²)O(n)
Optimal (single pass to the first mismatch)O(n)O(1)

1Brute force (try every single edit)

TimeO(n²)Up to n + 1 candidate strings are built and compared, each in O(n).
SpaceO(n)One candidate string of length n at a time.

Handle the two possible shapes separately. With equal lengths, count the positions that differ and require exactly one. With lengths off by one, try deleting each character of the longer string and check whether the result equals the shorter one.

  1. Let s be the shorter string (swap if needed). If t.length - s.length > 1, return false.
  2. Equal lengths: count mismatching positions and return count == 1.
  3. Length difference 1: for each index k in t, build t without index k; if it equals s, return true.
  4. Return false if no deletion worked.
class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s.length() > t.length()) return isOneEditDistance(t, s);
        if (t.length() - s.length() > 1) return false;
        if (s.length() == t.length()) {
            int diff = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != t.charAt(i)) diff++;
            }
            return diff == 1;
        }
        for (int k = 0; k < t.length(); k++) {
            String cand = t.substring(0, k) + t.substring(k + 1);
            if (cand.equals(s)) return true;
        }
        return false;
    }
}

2Optimal (single pass to the first mismatch)

TimeO(n)Each character is looked at a constant number of times: once in the scan and once in the final suffix comparison.
SpaceO(1)The suffix comparison can be done index by index, so only a few counters are used.

Make s the shorter string. Scan both strings together. At the first position where they differ, the one allowed edit must happen there: if the lengths are equal it is a replacement, so the remaining suffixes after it must match; otherwise it is an insertion into s, so s from this index must equal t from the next index. If the scan finds no mismatch, the strings are equal up to the shorter length, and the answer is true only when t has exactly one extra character at the end.

  1. If s is longer than t, swap them. If the length difference is above 1, return false.
  2. For i from 0 to s.length - 1: if s[i] != t[i], return s[i+1..] == t[i+1..] when lengths are equal, else s[i..] == t[i+1..].
  3. After the loop, return t.length == s.length + 1.
class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if (m > n) return isOneEditDistance(t, s);
        if (n - m > 1) return false;
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                int a = (m == n) ? i + 1 : i;
                int b = i + 1;
                while (a < m) {
                    if (s.charAt(a) != t.charAt(b)) return false;
                    a++;
                    b++;
                }
                return true;
            }
        }
        return n == m + 1;
    }
}

Edge cases to test

  • Equal strings: the answer is false
  • One string empty, the other of length 1: true; of length 2 or more: false
  • Lengths that differ by 2 or more: false without looking at the characters
  • The extra character is at the very start or the very end of the longer string
  • Two mismatches in strings of equal length: false

Hints

Hint 1

If the lengths differ by more than one, no single edit can fix it. Equal lengths can only be fixed by a replacement, lengths off by one only by an insertion or deletion.

Hint 2

Walk both strings until the first position where they differ. Everything before it already matches.

Hint 3

At the first mismatch, the rest must match exactly: compare s[i+1..] with t[i+1..] for equal lengths, or the shorter string's [i..] with the longer one's [i+1..]. If there is no mismatch at all, the answer depends only on whether the lengths differ by one.

FAQ

What is the best time complexity for One Edit Distance?

Optimal (single pass to the first mismatch) runs in O(n) time and O(1) extra space. Each character is looked at a constant number of times: once in the scan and once in the final suffix comparison.

Which pattern does One Edit Distance use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for One Edit Distance?

Yes. Brute force (try every single edit) takes O(n²) time and O(n) space. Handle the two possible shapes separately.

Which edge cases should I test for One Edit Distance?

Equal strings: the answer is false; One string empty, the other of length 1: true; of length 2 or more: false; Lengths that differ by 2 or more: false without looking at the characters; The extra character is at the very start or the very end of the longer string; Two mismatches in strings of equal length: false.