527. Word Abbreviation
基本的想法就是先计算出所有的abbr，然后把相同的abbr的index记录下来，然后依次扩展直到这一位消除了所有的相同的，这个video简直是神解释：https://www.youtube.com/watch?v=yAQMcGY4c90
class Solution(object):
def wordsAbbreviation(self, dict):
"""
:type dict: List[str]
:rtype: List[str]
"""
def get_abbreviation(word,old_abbreviation):
if old_abbreviation == '':
abbreviation = word[0] + str(len(word[1:-1])) + word[-1]
else:
for i in range(len(old_abbreviation)):
if old_abbreviation[i].isdigit():
abbreviation = word[:i+1] + str(len(word[i+1:-1])) + word[-1]
break
if len(word) <= len(abbreviation):
abbreviation = word
return abbreviation
abbreviations = [''] * len(words)
duplicates = collections.defaultdict(list)
for i,word in enumerate(words):
abbreviations[i] = get_abbreviation(word,'')
duplicates[abbreviations[i]] += i,
for i in range(len(abbreviations)):
if len(duplicates[abbreviations[i]]) == 1:
continue
else:
while len(duplicates[abbreviations[i]]) > 1:
for index in duplicates[abbreviations[i]]:
abbreviation = get_abbreviation(words[index], abbreviations[index])
abbreviations[index] = abbreviation
duplicates[abbreviation] += index,
return abbreviations
