Question

Formatted question description: https://leetcode.ca/all/161.html

 161	One Edit Distance

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

 Note:

 There are 3 possibilities to satisfy 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.

 @tag-dp

Algorithm

To determine whether the edit distance of two strings is 1, consider the following three situations:

The difference between the length of the two strings is greater than 1, and it returns False directly.
The difference between the lengths of the two strings is equal to 1. The longer string has one character removed, and the rest should be the same as the short string.
The difference between the length of the two strings is equal to 0, and the characters at the corresponding positions of the two strings can only be different in one place.

Code

Java

import java.util.Objects;

public class One_Edit_Distance {

    class Solution_true_dp {
        public boolean isOneEditDistance(String s, String t) {
            int m = s.length(), n = t.length(), i, j;
            int[][] dp = new int[m + 1][n + 1];
            for (i = 0; i <= m; i++)
                dp[i][0] = i;
            for (j = 0; j <= n; j++)
                dp[0][j] = j;
            for (i = 0; i < m; i++) {
                for (j = 0; j < n; j++) {
                    if (s.charAt(i) == t.charAt(j))
                        dp[i + 1][j + 1] = dp[i][j];
                    else {
                        dp[i + 1][j + 1] = Math.min(dp[i + 1][j], Math.min(dp[i][j + 1], dp[i][j])) + 1;
                    }
                }
            }
            return dp[m][n] == 1;
        }
    }

    public class Solution_dp {
        public boolean isOneEditDistance(String s, String t) {
            if (s.length() < t.length()) return isOneEditDistance(t, s); // so 't' is always the shorter one in below logic
            int m = s.length(), n = t.length(), diff = m - n;
            if (diff >= 2) return false;
            else if (diff == 1) {
                for (int i = 0; i < n; ++i) {
                    if (s.charAt(i) != t.charAt(i)) {
                        return s.substring(i + 1).equals(t.substring(i));
                    }
                }
                return true; // meaning, diff is happening at the final char
            } else {
                int cnt = 0;
                for (int i = 0; i < m; ++i) {
                    if (s.charAt(i) != t.charAt(i)) ++cnt;
                }
                return cnt == 1;
            }
        }
    }

    // best solution ha!
    public boolean isOneEditDistance(String s, String t) {
        for (int i = 0; i < Math.min(s.length(), t.length()); ++i) {
            if (s.charAt(i) != t.charAt(i)) {
                if (s.length() == t.length()) {
                    return Objects.equals(s.substring(i + 1), t.substring(i + 1));
                }
                if (s.length() < t.length()) {
                    return Objects.equals(s.substring(i), t.substring(i + 1));
                } else {
                    return Objects.equals(s.substring(i + 1), t.substring(i));
                }
            }
        }

        // case: abc, abcdefg
        return Math.abs((int)s.length() - (int)t.length()) == 1;

    }
}

// OJ: https://leetcode.com/problems/one-edit-distance/
// Time: O(MN)
// Space: O(min(M,N))
class Solution {
private:
    int editDistance(string &s, string &t) {
        if (s.size() < t.size()) swap(s, t);
        int M = s.size(), N = t.size();
        vector<int> dp(N + 1, 0);
        for (int i = 1; i <= N; ++i) dp[i] = i;
        for (int i = 1; i <= M; ++i) {
            int pre = dp[0];
            dp[0] = i;
            for (int j = 1; j <= N; ++j) {
                int tmp = dp[j];
                if (s[i - 1] == t[j - 1]) dp[j] = pre;
                else dp[j] = min(pre, min(dp[j - 1], dp[j])) + 1;
                pre = tmp;
            }
        }
        return dp[N];
    }
public:
    bool isOneEditDistance(string s, string t) {
        return editDistance(s, t) == 1;
    }
};

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        if len(s) < len(t):
            return self.isOneEditDistance(t, s)
        m, n = len(s), len(t)
        if m - n > 1:
            return False
        for i, c in enumerate(t):
            if c != s[i]:
                return s[i + 1 :] == t[i + 1 :] if m == n else s[i + 1 :] == t[i:]
        return m == n + 1

############

class Solution(object):
  def isOneEditDistance(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    if len(s) >= len(t):
      i = 0
      while i < len(t) and s[i] == t[i]:
        i += 1
      return s != t and (s[i + 1:] == t[i:] if len(s) != len(t) else s[i + 1:] == t[i + 1:])
    else:
      return self.isOneEditDistance(t, s)

161 - One Edit Distance

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions