One Edit Distance
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
swith 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
tto the end ofplanegivesplanet, 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^4sandtconsist 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n²)Up to n + 1 candidate strings are built and compared, each in O(n).O(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.
- Let
sbe the shorter string (swap if needed). Ift.length - s.length > 1, return false. - Equal lengths: count mismatching positions and return
count == 1. - Length difference 1: for each index
kint, buildtwithout indexk; if it equalss, return true. - 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;
}
}class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
if len(s) > len(t):
return self.isOneEditDistance(t, s)
if len(t) - len(s) > 1:
return False
if len(s) == len(t):
diff = 0
for i in range(len(s)):
if s[i] != t[i]:
diff += 1
return diff == 1
for k in range(len(t)):
if t[:k] + t[k + 1:] == s:
return True
return Falseclass Solution {
public:
bool isOneEditDistance(string s, string t) {
if (s.size() > t.size()) return isOneEditDistance(t, s);
if (t.size() - s.size() > 1) return false;
if (s.size() == t.size()) {
int diff = 0;
for (size_t i = 0; i < s.size(); i++) {
if (s[i] != t[i]) diff++;
}
return diff == 1;
}
for (size_t k = 0; k < t.size(); k++) {
string cand = t.substr(0, k) + t.substr(k + 1);
if (cand == s) return true;
}
return false;
}
};function isOneEditDistance(s, t) {
if (s.length > t.length) return isOneEditDistance(t, s);
if (t.length - s.length > 1) return false;
if (s.length === t.length) {
let diff = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] !== t[i]) diff++;
}
return diff === 1;
}
for (let k = 0; k < t.length; k++) {
const cand = t.slice(0, k) + t.slice(k + 1);
if (cand === s) return true;
}
return false;
}2Optimal (single pass to the first mismatch)
O(n)Each character is looked at a constant number of times: once in the scan and once in the final suffix comparison.O(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.
- If
sis longer thant, swap them. If the length difference is above 1, return false. - For
ifrom 0 tos.length - 1: ifs[i] != t[i], returns[i+1..] == t[i+1..]when lengths are equal, elses[i..] == t[i+1..]. - 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;
}
}class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
if m > n:
return self.isOneEditDistance(t, s)
if n - m > 1:
return False
for i in range(m):
if s[i] != t[i]:
a = i + 1 if m == n else i
b = i + 1
while a < m:
if s[a] != t[b]:
return False
a += 1
b += 1
return True
return n == m + 1class Solution {
public:
bool isOneEditDistance(string s, string t) {
int m = s.size(), n = t.size();
if (m > n) return isOneEditDistance(t, s);
if (n - m > 1) return false;
for (int i = 0; i < m; i++) {
if (s[i] != t[i]) {
int a = (m == n) ? i + 1 : i;
int b = i + 1;
while (a < m) {
if (s[a] != t[b]) return false;
a++;
b++;
}
return true;
}
}
return n == m + 1;
}
};function isOneEditDistance(s, t) {
const m = s.length, n = t.length;
if (m > n) return isOneEditDistance(t, s);
if (n - m > 1) return false;
for (let i = 0; i < m; i++) {
if (s[i] !== t[i]) {
let a = (m === n) ? i + 1 : i;
let b = i + 1;
while (a < m) {
if (s[a] !== t[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.