难度: Medium
Submission
运行时间: 67 ms
内存: 26.0 MB
class ValidWordAbbr:
def __init__(self, dictionary: List[str]):
self.dic = defaultdict(list)
for char in dictionary:
l = len(char)
key = char[0] + str(l - 2) + char[l - 1]
if l <= 2:
self.dic[char].append(char)
else:
self.dic[key].append(char)
def isUnique(self, word: str) -> bool:
l = len(word)
key = word[0] + str(l - 2) + word[l - 1]
if l <= 2:
return True
if key in self.dic:
if len(self.dic[key]) == 1 and self.dic[key][0] == word:
return True
else:
return False
return True
# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)
Explain
该题解的思路是将单词转换为唯一缩写形式作为哈希表的键，将原单词存储在对应的值列表中。对于查询单词，先计算其唯一缩写，然后在哈希表中查找对应的值列表。如果列表长度为1且与查询单词相同，则认为该单词的缩写是唯一的；如果列表长度大于1或者列表中的单词与查询单词不同，则认为该单词的缩写不唯一。对于长度小于等于2的单词，直接认为其缩写是唯一的。
时间复杂度: 构造函数: O(n), isUnique 函数: 平均 O(1)，最坏 O(n)
空间复杂度: O(n)
class ValidWordAbbr:
def __init__(self, dictionary: List[str]):
self.dic = defaultdict(list)
for char in dictionary:
l = len(char)
key = char[0] + str(l - 2) + char[l - 1] # 计算单词的唯一缩写
if l <= 2:
self.dic[char].append(char) # 对于长度小于等于2的单词，直接存储单词本身
else:
self.dic[key].append(char) # 将单词存储在对应唯一缩写的值列表中
def isUnique(self, word: str) -> bool:
l = len(word)
key = word[0] + str(l - 2) + word[l - 1] # 计算查询单词的唯一缩写
if l <= 2:
return True # 对于长度小于等于2的单词，直接认为其缩写是唯一的
if key in self.dic:
if len(self.dic[key]) == 1 and self.dic[key][0] == word: # 如果值列表长度为1且与查询单词相同，则缩写唯一
return True
else:
return False # 如果值列表长度大于1或者列表中的单词与查询单词不同，则缩写不唯一
return True # 如果哈希表中不存在该唯一缩写，则认为缩写是唯一的
# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)
Explore
选择单词的首尾字符和长度作为缩写的策略是因为这样简洁且通常能保持单词的唯一性，同时减少存储空间的需求。然而，这种策略在某些情况下会导致高冲突率，尤其是在单词长度相同且首尾字符也相同的情况下。例如，单词'banner'和'boomer'都将缩写为'b4r'，这会导致冲突。
对于长度小于等于2的单词，其缩写形式（如果按照首尾字符和中间字符数量来定义）实际上与原单词相同，因此使用单词本身作为键值可以简化处理流程，并且在这种情况下，单词本身就是其唯一的标识，不需要再进行缩写。
当哈希表中不存在查询单词的唯一缩写键时，直接返回True通常是安全的，因为这意味着在初始化字典时没有任何其他单词具有相同的缩写形式。然而，这种假设的前提是所有可能影响结果的单词都已经在初始化时被考虑了。如果字典在之后被修改，或者在初始化时未包括所有相关单词，则这种假设可能不安全。
如果存在多个相同的单词，它们会被添加到哈希表的同一键下的值列表中。这本身不会影响哈希表的构建，但会影响查询结果的正确性。在`isUnique`函数中，如果某个缩写下的单词列表包含多个相同的单词，这可能导致错误地认为这些单词的缩写不是唯一的，即使它们实际上是相同的单词。因此，处理方式应当在添加单词时检查是否已存在相同单词，以避免这种情况。