难度: Medium
Submission
运行时间: 23 ms
内存: 16.0 MB
class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
len_s = len(s)
len_t = len(t)
for i in range(min(len_s, len_t)):
if (s[i] != t[i]):
if len_s == len_t:
return s[i + 1:] == t[i + 1:]
elif len_s < len_t:
return s[i: ] == t[i + 1:]
else:
return s[i+1:] == t[i:]
if abs(len_s - len_t) == 1:
return True
else:
return False
Explain
该题解的思路是逐个比较两个字符串 s 和 t 的字符，找到第一个不同的位置，然后根据两个字符串的长度关系进行判断：1. 如果两个字符串长度相同，则判断剩余部分是否完全相同；2. 如果 s 比 t 短，则判断 s 剩余部分是否与 t 剩余部分（从不同字符的下一个位置开始）完全相同；3. 如果 s 比 t 长，则判断 s 剩余部分（从不同字符的下一个位置开始）是否与 t 剩余部分完全相同。最后，如果两个字符串长度差正好为1，且上述三种情况都不满足，则说明相隔为 1 的编辑距离。
时间复杂度: O(min(len_s, len_t))
空间复杂度: O(1)
class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
len_s = len(s)
len_t = len(t)
for i in range(min(len_s, len_t)):
# 找到第一个不同的字符
if (s[i] != t[i]):
if len_s == len_t:
# 如果两个字符串长度相同，判断剩余部分是否完全相同
return s[i + 1:] == t[i + 1:]
elif len_s < len_t:
# 如果 s 比 t 短，判断 s 剩余部分是否与 t 剩余部分（从不同字符的下一个位置开始）完全相同
return s[i: ] == t[i + 1:]
else:
# 如果 s 比 t 长，判断 s 剩余部分（从不同字符的下一个位置开始）是否与 t 剩余部分完全相同
return s[i+1:] == t[i:]
# 如果遍历结束都没有找到不同的字符，则判断两个字符串长度差是否为1
if abs(len_s - len_t) == 1:
return True
else:
return False
Explore
该算法的目标是判断两个字符串之间是否存在恰好一次的编辑操作（包括插入一个字符、删除一个字符或修改一个字符）使得两者相等。如果两个字符串完全相同且长度相等，意味着它们之间不需要任何编辑操作就已经相等了。因此，在这种情况下，它们的编辑距离为0而不是1，所以函数返回 False，因为我们要寻找的是编辑距离恰好为1的情况。
是的，这种做法充分考虑了题目的要求。当两个字符串的长度差异大于1时，无法通过单一的编辑操作（仅一次插入、删除或修改）来使字符串变得相等。因此，如果长度差大于1，那么它们的编辑距离至少为2。算法在这种情况下返回 False 是正确的，因为我们只关心那些编辑距离恰好为1的情况。
在找到第一个不同的字符后，直接比较剩余部分的字符串是基于假设：如果两个字符串在某处有一个字符不同，那么剩余部分必须完全相同，才能保证总的编辑距离为1（即仅这一个不同的位置是通过一次编辑得到的）。直接比较字符串是基于字符串的字面值，不依赖于字符的特殊编码或属性。因此，这种比较方法是有效的，并且能够正确处理包含任何类型字符的字符串，包括特殊字符或多语言字符。
该算法适用于所有类型的字符串输入，包括ASCII字符、Unicode字符、特殊符号以及多语言文本。算法基于Python的字符串处理功能，这些功能良好地支持多种字符编码。由于算法是逐字符比较，并检查剩余子字符串是否相等，因此它能够正确处理包含任何字符的字符串。不管字符串包含何种字符，只要它们的编辑距离恰好为1，该算法都能正确返回 True。