难度: Hard
Submission
运行时间: 60 ms
内存: 20.2 MB
class Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
cache = {}
ret = {}
def ga(w,np):
n = len(w)-1-np
return w[0:np] + str(len(w)-1-np) + w[-1] if n > 1 else w
def add(w):
if len(w) < 4:
ret[w]=w
else:
for np in range(1,len(w)-1):
a = ga(w,np)
if a in cache:
if cache[a]:
w2 = cache[a]
cache[a] = ''
add(w2)
else:
cache[a] = w
break
for w in words:
add(w)
for k,v in cache.items():
if v:
ret[v]=k
return [ret[w] for w in words]
Explain
此题解的核心思路是缩写给定列表中的单词。如果单词长度小于4，不进行缩写。对于其他单词，从最短可能的缩写开始尝试，直到找到一个不与其他单词的缩写冲突的缩写。此过程使用两个主要数据结构：'cache'用来存储每个缩写对应的单词（如果存在冲突，则设置为空字符串），'ret'用来存储每个单词对应的最终缩写结果。函数 'ga' 用于生成一个单词的缩写，'add' 函数尝试为一个单词找到一个合适的缩写并处理冲突。最后，根据输入单词的顺序返回缩写结果。
时间复杂度: O(n * k^2) 其中 n 是单词数量，k 是单词的平均长度
空间复杂度: O(n * k) 其中 n 是单词数量，k 是单词的平均长度
class Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
cache = {} # 缓存缩写到单词的映射
ret = {} # 存储最终每个单词的缩写
def ga(w, np): # 生成单词 w 的缩写，np 是保留的前缀长度
n = len(w) - 1 - np
return w[0:np] + str(len(w) - 1 - np) + w[-1] if n > 1 else w
def add(w): # 为单词 w 寻找不冲突的缩写
if len(w) < 4:
ret[w] = w
else:
for np in range(1, len(w) - 1):
a = ga(w, np)
if a in cache:
if cache[a]:
w2 = cache[a]
cache[a] = ''
add(w2) # 处理冲突，重新为 w2 寻找缩写
else:
cache[a] = w
break
for w in words:
add(w) # 处理所有单词
for k, v in cache.items():
if v:
ret[v] = k # 将无冲突的缩写存入 ret
return [ret[w] for w in words] # 根据原始单词顺序返回缩写结果
Explore
`np`参数在函数`ga`中代表单词的前缀长度，这意味着在生成缩写时会保留单词的前`np`个字符。通过改变`np`的值，可以生成不同长度的缩写。这个值通常从1开始增加，尝试生成尽可能短的有效缩写，直到找到一个不与任何其他单词的缩写冲突的缩写为止。
为了防止错误覆盖或丢失数据，当缩写`a`已存在于`cache`中并且与另一个单词冲突时，原始代码不会简单地覆盖缩写。相反，如果`cache[a]`已经有值，它会将该值设置为空字符串，并对原来的单词重新执行缩写查找。这确保了所有单词都有机会找到一个唯一的缩写，避免了数据的丢失。
将`cache[a]`设置为空字符串是为了标记这个缩写已经引起了冲突，不能被任何单词使用。这样做的具体好处是，它迫使代码重新为与此缩写冲突的所有单词寻找新的缩写，确保每个单词都能最终拥有一个独一无二的缩写。此外，这种方法也帮助避免了无限循环或重复处理同一个冲突。
递归调用`add(w2)`来处理冲突可能导致几个潜在的风险或效率问题：1. **栈溢出**：如果单词数量很多或冲突频繁发生，递归深度可能会变得很深，这可能导致栈溢出错误。2. **重复计算**：递归过程中可能多次处理同一单词，特别是当多个单词频繁冲突时，这会导致效率低下。3. **时间复杂度增加**：每次冲突发生时，都需要重新为单词找到一个新的缩写，这可能导致整个算法的时间复杂度大幅增加，尤其是在单词数目较多的情况下。