161.One-Edit-Distance

161. 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;
}