161. One Edit Distance
給定兩個字符串 s 和 t，如果它們之間的編輯距離為 1，則返回 true，否則返回 false。
當你可以進行以下任意一種操作時，字符串 s 被認為與字符串 t 之間的編輯距離為 1：在 s 中插入恰好一個字符以得到 t。
從 s 中刪除恰好一個字符以得到 t。
用不同的字符替換 s 中恰好一個字符以得到 t。
範例 ：
輸入：s = "ab", t = "acb"
輸出：true
解釋：我們可以在 s 中插入字符 'c' 以得到 t。
Python
class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
# If the length difference is greater than 1, they can't be one edit distance apart
if abs(m - n) > 1:
return False
# Make sure s is the shorter string
if m > n:
s, t = t, s
m, n = n, m
i, j, foundDifference = 0, 0, False
while i < m and j < n:
if s[i] != t[j]:
if foundDifference:
return False
foundDifference = True
# If lengths are different, move the pointer of the longer string
if m != n:
j += 1
continue
i += 1
j += 1
# If there was no difference found, check if the length difference is exactly one
if not foundDifference and m == n:
return False
return True
16.58MB, 40ms
C++
class Solution {
public:
bool isOneEditDistance(string s, string t) {
int m = s.length(), n = t.length();
// If the length difference is greater than 1, they can't be one edit distance apart
if (abs(m - n) > 1) return false;
// Make sure s is the shorter string
if (m > n) {
swap(s, t);
swap(m, n);
}
bool foundDifference = false;
for (int i = 0, j = 0; i < m; ++i, ++j) {
if (s[i] != t[j]) {
if (foundDifference) return false;
foundDifference = true;
// If lengths are different, move the pointer of the longer string
if (m != n) --i;
}
}
// If there was no difference found, check if the length difference is exactly one
return foundDifference || (m + 1 == n);
}
};
7.68MB, 4ms
Javascript
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isOneEditDistance = function(s, t) {
const m = s.length, n = t.length;
// If the length difference is greater than 1, they can't be one edit distance apart
if (Math.abs(m - n) > 1) return false;
// Make sure s is the shorter string
if (m > n) {
[s, t] = [t, s];
}
const len1 = s.length;
const len2 = t.length;
let foundDifference = false;
for (let i = 0, j = 0; i < len1; i++, j++) {
if (s[i] !== t[j]) {
if (foundDifference) return false;
foundDifference = true;
// If lengths are different, move the pointer of the longer string
if (len1 !== len2) i--;
}
}
// If there was no difference found, check if the length difference is exactly one
return foundDifference || len1 + 1 === len2;
};
49.82MB, 59ms
