# Question

Formatted question description: https://leetcode.ca/all/161.html

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

• Insert exactly one character into s to get t.
• Delete exactly one character from s to get t.
• Replace exactly one character of s with a different character to get t.

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.


Example 2:

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.


Constraints:

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

# Algorithm

### Step 1: Ensure s is the Longer String

if len(s) < len(t):
return self.isOneEditDistance(t, s)


If s is shorter than t, the method recursively calls itself with the arguments reversed to ensure that s is always the longer string. This simplification allows the algorithm to focus on deletion or replacement operations without separately handling insertions.

### Step 2: Check for Significant Length Differences

m, n = len(s), len(t)
if m - n > 1:
return False


If the length difference between s and t is greater than one, it’s impossible for them to be one edit distance apart. In such cases, the method immediately returns False.

### Step 3: Identify the Type of Edit Required

for i, c in enumerate(t):
if c != s[i]:
return s[i + 1 :] == t[i + 1 :] if m == n else s[i + 1 :] == t[i:]


The method iterates through the characters of the shorter string t. If it encounters a character c that doesn’t match the corresponding character in s, it then checks the type of edit required:

• If s and t are of equal length (m == n), the method checks for a replacement operation by comparing the substrings of s and t after the differing character.
• If s is longer than t (m > n), the method checks for a deletion operation in s by comparing the substring of s after the differing character with the rest of t.

If either condition is true, the strings are one edit distance apart, and the method returns True.

### Step 4: Handle Edge Cases

return m == n + 1


After the loop, if no differing characters were found, there are a few possible scenarios:

• s is exactly one character longer than t (m == n + 1), implying a deletion operation is needed to match t with s. The method returns True because they are one edit distance apart.
• s and t are of the same length but identical, which means they are not one edit distance apart. The method correctly returns False due to the check at the beginning.
• s and t differ in length by more than one character, which was already handled earlier in the method.

# Code

• import java.util.Objects;

public class One_Edit_Distance {

// best solution ha!
public boolean isOneEditDistance(String s, String t) {
for (int i = 0; i < Math.min(s.length(), t.length()); ++i) {
if (s.charAt(i) != t.charAt(i)) {
if (s.length() == t.length()) {
return Objects.equals(s.substring(i + 1), t.substring(i + 1));
}
if (s.length() < t.length()) {
return Objects.equals(s.substring(i), t.substring(i + 1));
} else {
return Objects.equals(s.substring(i + 1), t.substring(i));
}
}
}

// case: abc, abcdefg
return Math.abs((int)s.length() - (int)t.length()) == 1;

}

class Solution_true_dp {
public boolean isOneEditDistance(String s, String t) {
int m = s.length(), n = t.length(), i, j;
int[][] dp = new int[m + 1][n + 1];
for (i = 0; i <= m; i++)
dp[i][0] = i;
for (j = 0; j <= n; j++)
dp[0][j] = j;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (s.charAt(i) == t.charAt(j))
dp[i + 1][j + 1] = dp[i][j];
else {
dp[i + 1][j + 1] = Math.min(dp[i + 1][j], Math.min(dp[i][j + 1], dp[i][j])) + 1;
}
}
}
return dp[m][n] == 1;
}
}

public class Solution_dp {
public boolean isOneEditDistance(String s, String t) {
if (s.length() < t.length()) return isOneEditDistance(t, s); // so 't' is always the shorter one in below logic
int m = s.length(), n = t.length(), diff = m - n;
if (diff >= 2) return false;
else if (diff == 1) {
for (int i = 0; i < n; ++i) {
if (s.charAt(i) != t.charAt(i)) {
return s.substring(i + 1).equals(t.substring(i));
}
}
return true; // meaning, diff is happening at the final char
} else {
int cnt = 0;
for (int i = 0; i < m; ++i) {
if (s.charAt(i) != t.charAt(i)) ++cnt;
}
return cnt == 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 (m - n > 1) {
return false;
}
for (int i = 0; i < n; ++i) {
if (s.charAt(i) != t.charAt(i)) {
if (m == n) {
return s.substring(i + 1).equals(t.substring(i + 1));
}
return s.substring(i + 1).equals(t.substring(i));
}
}
return m == n + 1;
}
}

• // OJ: https://leetcode.com/problems/one-edit-distance/
// Time: O(MN)
// Space: O(min(M,N))
class Solution {
private:
int editDistance(string &s, string &t) {
if (s.size() < t.size()) swap(s, t);
int M = s.size(), N = t.size();
vector<int> dp(N + 1, 0);
for (int i = 1; i <= N; ++i) dp[i] = i;
for (int i = 1; i <= M; ++i) {
int pre = dp[0];
dp[0] = i;
for (int j = 1; j <= N; ++j) {
int tmp = dp[j];
if (s[i - 1] == t[j - 1]) dp[j] = pre;
else dp[j] = min(pre, min(dp[j - 1], dp[j])) + 1;
pre = tmp;
}
}
return dp[N];
}
public:
bool isOneEditDistance(string s, string t) {
return editDistance(s, t) == 1;
}
};

• class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
if len(s) < len(t): # goal is to ensure t is always the shorter one
return self.isOneEditDistance(t, s)
m, n = len(s), len(t)
if m - n > 1:
# case: abc, abcdefg, return false
return False
for i, c in enumerate(t):
if c != s[i]:
return s[i + 1 :] == t[i + 1 :] if m == n else s[i + 1 :] == t[i:]
# case: abc, abcd. return true
# case: abc, abc. the same 2 strings should return false
# case: abc, abcdefg, return false
return m == n + 1

############

class Solution(object):
def isOneEditDistance(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) >= len(t):
i = 0
while i < len(t) and s[i] == t[i]:
i += 1
return s != t and (s[i + 1:] == t[i:] if len(s) != len(t) else s[i + 1:] == t[i + 1:])
else:
return self.isOneEditDistance(t, s)


• func isOneEditDistance(s string, t string) bool {
m, n := len(s), len(t)
if m < n {
return isOneEditDistance(t, s)
}
if m-n > 1 {
return false
}
for i := range t {
if s[i] != t[i] {
if m == n {
return s[i+1:] == t[i+1:]
}
return s[i+1:] == t[i:]
}
}
return m == n+1
}

• function isOneEditDistance(s: string, t: string): boolean {
const [m, n] = [s.length, t.length];
if (m < n) {
return isOneEditDistance(t, s);
}
if (m - n > 1) {
return false;
}
for (let i = 0; i < n; ++i) {
if (s[i] !== t[i]) {
return s.slice(i + 1) === t.slice(i + (m === n ? 1 : 0));
}
}
return m === n + 1;
}