161.One-Edit-Distance.md

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