# 161.One-Edit-Distance

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/one-edit-distance/

## ้ข็ฎๆ่ฟฐ

``````Given two strings s and t, determine if they are both one edit distance apart.

Note:
There are 3 possiblities to satisify one edit distance apart:

Insert a character into s to get t
Delete a character from s to get t
Replace a character of s 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 = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:

Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.``````

## ไปฃ็ 

### Approach #1 One pass

``````class Solution {
public boolean isOneEditDistance(String s, String t) {
int ns = s.length();
int nt = t.length();

if (nt < ns) {
return isOneEditDistance(t, s);
}

if (nt - ns > 1)        return false;

for (int i = 0; i < ns; i++) {
if (s.charAt(i) != t.charAt(i)) {
if (ns == nt) {
return s.substring(i + 1).equals(t.substring(i + 1));
} else {
return s.substring(i).equals(t.substring(i + 1));
}
}
}

return (ns + 1 == nt);
}
}``````

### Approach #2 Two Pointers

``````public boolean isOneEditDistance(String s, String t) {
int m = s.length(), n = t.length();
if (Math.abs(m - n) > 1) return false;
int k = Math.min(m, n);
int i = 0, j = 0;
while (i < k && s.charAt(i) == t.charAt(i)) ++i;
while (j < k - i && s.charAt(m - 1 - j) == t.charAt(n - 1 - j)) ++j;
return m + n - k - 1 == i + j;
}``````

Last updated