Welcome to Subscribe On Youtube

Question

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

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

  • Insert exactly one character into s to get t.
  • Delete exactly one character from s to get t.
  • Replace exactly one character of s with a different character 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 = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

 

Constraints:

  • 0 <= s.length, t.length <= 104
  • s and t consist of lowercase letters, uppercase letters, and digits.

Algorithm

Step 1: Ensure s is the Longer String

if len(s) < len(t):
    return self.isOneEditDistance(t, s)

If s is shorter than t, the method recursively calls itself with the arguments reversed to ensure that s is always the longer string. This simplification allows the algorithm to focus on deletion or replacement operations without separately handling insertions.

Step 2: Check for Significant Length Differences

m, n = len(s), len(t)
if m - n > 1:
    return False

If the length difference between s and t is greater than one, it’s impossible for them to be one edit distance apart. In such cases, the method immediately returns False.

Step 3: Identify the Type of Edit Required

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:]

The method iterates through the characters of the shorter string t. If it encounters a character c that doesn’t match the corresponding character in s, it then checks the type of edit required:

  • If s and t are of equal length (m == n), the method checks for a replacement operation by comparing the substrings of s and t after the differing character.
  • If s is longer than t (m > n), the method checks for a deletion operation in s by comparing the substring of s after the differing character with the rest of t.

If either condition is true, the strings are one edit distance apart, and the method returns True.

Step 4: Handle Edge Cases

return m == n + 1

After the loop, if no differing characters were found, there are a few possible scenarios:

  • s is exactly one character longer than t (m == n + 1), implying a deletion operation is needed to match t with s. The method returns True because they are one edit distance apart.
  • s and t are of the same length but identical, which means they are not one edit distance apart. The method correctly returns False due to the check at the beginning.
  • s and t differ in length by more than one character, which was already handled earlier in the method.

Code

  • import java.util.Objects;

public class One_Edit_Distance {

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

    }

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

//////

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return isOneEditDistance(t, s);
        }
        if (m - n > 1) {
            return false;
        }
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                }
                return s.substring(i + 1).equals(t.substring(i));
            }
        }
        return m == n + 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): # goal is to ensure t is always the shorter one
            return self.isOneEditDistance(t, s)
        m, n = len(s), len(t)
        if m - n > 1:
            # case: abc, abcdefg, return false
            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:]
        # case: abc, abcd. return true
        # case: abc, abc. the same 2 strings should return false
        # case: abc, abcdefg, return false
        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)


  • func isOneEditDistance(s string, t string) bool {
	m, n := len(s), len(t)
	if m < n {
		return isOneEditDistance(t, s)
	}
	if m-n > 1 {
		return false
	}
	for i := range t {
		if s[i] != t[i] {
			if m == n {
				return s[i+1:] == t[i+1:]
			}
			return s[i+1:] == t[i:]
		}
	}
	return m == n+1
}

  • function isOneEditDistance(s: string, t: string): boolean {
    const [m, n] = [s.length, t.length];
    if (m < n) {
        return isOneEditDistance(t, s);
    }
    if (m - n > 1) {
        return false;
    }
    for (let i = 0; i < n; ++i) {
        if (s[i] !== t[i]) {
            return s.slice(i + 1) === t.slice(i + (m === n ? 1 : 0));
        }
    }
    return m === n + 1;
}

All Problems

All Solutions