I have to say I was surprised that my straight forward solution can be accepted and I am looking for a proper more efficient solution.
The idea is simple:
abbreviate all existing word and append its index into a dictionary of list so that the words has the same abbr would be grouped together. Make sure you save the index in the words indicates the next position you start abbreviate the word so we could continue later on.
e.g. hello -> h3o with index 2, if this word has already existed, next one would be he2o with index 3.
keep popping items from the dictionary. There are two situations
- If there is only one item in the dictionary we can take it as the final result.
- If there are more than one items in the list means we need to move the prefix forward.
class Solution(object): def wordsAbbreviation(self, words): index = defaultdict(list) res = [None] * len(words) for idx, word in enumerate(words): if len(word) < 4: res[idx] = word else: index[word + str(len(word[1: -1])) + word[-1]].append((idx, 2)) while index: abbr, indexes = index.popitem() if len(indexes) == 1: res[indexes] = abbr continue for idx, i in indexes: if i == len(words[idx]) - 2: res[idx] = words[idx] else: word = words[idx] index[word[:i] + str(len(word) - 1 - i) + word[-1]].append((idx, i + 1)) return res