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 gett
. - Delete exactly one character from
s
to gett
. - Replace exactly one character of
s
with a different character to gett
.
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
andt
consist of lowercase letters, uppercase letters, and digits.
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
-
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): # t is the shorter one 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:] # case: abc, abcd. return true # case: abc and 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 }