难度: Medium
Submission
运行时间: 263 ms
内存: 26.5 MB
class Solution:
def differByOne(self, dict: List[str]) -> bool:
base,mod = 27,10**18+3
n = len(dict[0])
has = set()
for s in dict:
ss = [ord(x)-ord('a')+1 for x in s]#把字符串都转成数字来进行字符串哈希，+1是为了留空
pre = 0
for i in ss: pre = (pre*base+i)%mod
hou = 1
for i in range(n-1,-1,-1):#枚举所有可以留空的位置
lin = (pre-hou*ss[i])%mod
if lin in has:return True
has.add(lin)
hou = (hou*base)%mod
return False
Explain
这道题的思路是使用字符串哈希的方法。对于每个字符串，计算其哈希值，并尝试将每个位置上的字符替换为空（通过减去该字符对应的哈希值），检查替换后的哈希值是否在之前出现过。如果出现过，说明存在两个字符串仅在一个字符上不同，返回true。否则，继续检查下一个字符串。
时间复杂度: O(nm)
空间复杂度: O(nm)
class Solution:
def differByOne(self, dict: List[str]) -> bool:
base,mod = 27,10**18+3 # 定义哈希基数和模数
n = len(dict[0]) # 获取字符串长度
has = set() # 初始化哈希集合
for s in dict: # 遍历每个字符串
ss = [ord(x)-ord('a')+1 for x in s] # 将字符串转换为数字数组
pre = 0 # 初始化前缀哈希值
for i in ss: pre = (pre*base+i)%mod # 计算字符串的哈希值
hou = 1 # 初始化后缀乘数
for i in range(n-1,-1,-1): # 从后向前遍历字符
lin = (pre-hou*ss[i])%mod # 计算去掉当前字符后的哈希值
if lin in has: return True # 如果哈希值已存在，返回true
has.add(lin) # 将哈希值添加到集合中
hou = (hou*base)%mod # 更新后缀乘数
return False # 如果没有找到符合条件的字符串，返回false
Explore
在字符串哈希中，`base`被用于将每个字符转换成一个数值，并保证不同字符的数值不会冲突。选择27作为`base`是因为英文字母表中有26个字母，加上1则可以确保每个字符都有一个独立的数值，从1到26。至于`mod`，它是用来防止哈希值过大而溢出的同时降低哈希冲突的概率。选择10**18+3是因为这是一个非常大的素数，使用大的素数作为模数可以有效降低哈希冲突的风险。
在这个公式中，`pre`是整个字符串的哈希值，`ss[i]`是第i个字符的数值，`hou`是从当前字符到字符串末尾的部分的权重。通过`pre-hou*ss[i]`计算的是去除第i个字符影响后的哈希值。这里的`hou*ss[i]`计算的是第i个字符对哈希值的贡献，从总哈希值中减去这部分可以得到不包含这个字符的哈希值。最后取模操作是为了防止数值溢出并维持哈希值的一致性。
是的，使用哈希方法处理字符串时，总存在一定的哈希冲突风险，即不同的字符串可能有相同的哈希值（假阳性）。尽管选择了大的素数作为模数以减少这种风险，但理论上仍然可能发生。在实际应用中，如果要完全避免这一风险，可能需要在发现哈希值冲突时进一步检查两个字符串的具体内容。
实际上，除了使用哈希方法外，还可以使用简单的双层循环比较方法来解决这个问题。即对于字典中的每一对字符串，逐个比较它们的字符，计算不同字符的数量。如果恰好只有一个字符不同，则直接返回true。这种方法的时间复杂度是O(n*m^2)，其中n是字符串的平均长度，m是字典中字符串的数量。这种方法在m不大时是可行的，但在m很大或字符串长度很长时，效率较低，不如哈希方法高效。