Skip to content

161. One Edit Distance 👍

  • Time: $O(\min(|\texttt{s}|, |\texttt{t}|))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  bool isOneEditDistance(string s, string t) {
    const int m = s.length();
    const int n = t.length();
    if (m > n)  // Make sure that |s| <= |t|.
      return isOneEditDistance(t, s);

    for (int i = 0; i < m; ++i)
      if (s[i] != t[i]) {
        if (m == n)
          return s.substr(i + 1) == t.substr(i + 1);  // Replace s[i] with t[i].
        return s.substr(i) == t.substr(i + 1);        // Delete t[i].
      }

    return m + 1 == n;  // Delete t[-1].
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public boolean isOneEditDistance(String s, String t) {
    final int m = s.length();
    final int n = t.length();
    if (m > n) // Make sure that |s| <= |t|.
      return isOneEditDistance(t, s);

    for (int i = 0; i < m; ++i)
      if (s.charAt(i) != t.charAt(i)) {
        if (m == n)
          return s.substring(i + 1).equals(t.substring(i + 1)); // Replace s[i] with t[i].
        return s.substring(i).equals(t.substring(i + 1));       // Delete t[i].
      }

    return m + 1 == n; // Delete t[-1].
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def isOneEditDistance(self, s: str, t: str) -> bool:
    m = len(s)
    n = len(t)
    if m > n:  # Make sure that |s| <= |t|.
      return self.isOneEditDistance(t, s)

    for i in range(m):
      if s[i] != t[i]:
        if m == n:
          return s[i + 1:] == t[i + 1:]  # Replace s[i] with t[i].
        return s[i:] == t[i + 1:]  # Delete t[i].

    return m + 1 == n  # Delete t[-1].