Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

161. One Edit Distance

Time: $O(\min(|\texttt{s}|, |\texttt{t}|))$

Space: $O(1)$

			


class Solution {
 public:
  bool isOneEditDistance(string s, string t) {
    const int m = s.length();
    const int n = t.length();
    if (m > n)  // Make sure len(s) <= len(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]
  }
};




			


class Solution {
  public boolean isOneEditDistance(String s, String t) {
    final int m = s.length();
    final int n = t.length();
    if (m > n) // Make sure len(s) <= len(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]
  }
}




			


class Solution:
  def isOneEditDistance(self, s: str, t: str) -> bool:
    m = len(s)
    n = len(t)
    if m > n:  # Make sure len(s) <= len(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]