## 题目描述：

LeetCode 527. Word Abbreviation

Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below.

1. Begin with the first character and then the number of characters abbreviated, which followed by the last character.
2. If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words.
3. If the abbreviation doesn't make the word shorter, then keep it as original.

Example:

```Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
```

Note:

1. Both n and the length of each word will not exceed 400.
2. The length of each word is greater than 1.
3. The words consist of lowercase English letters only.
4. The return answers should be in the same order as the original array.

## 题目大意：

1. n和每个单词的长度不超过400。
2. 每个单词的长度大于1。
3. 单词只包含小写英文字母。
4. 返回结果应与原始顺序相同。

## 解题思路：

```利用字典dmap维护原始字符串word到压缩字符串abbr的映射

## Python代码：

``````class Solution(object):
def abbr(self, word, size):
if len(word) - size <= 3: return word
return word[:size + 1] + str(len(word) - size - 2) + word[-1]

def solve(self, dict, size):
dlist = collections.defaultdict(list)
for word in dict:
dlist[self.abbr(word, size)].append(word)
for abbr, wlist in dlist.iteritems():
if len(wlist) == 1:
self.dmap[wlist[0]] = abbr
else:
self.solve(wlist, size + 1)

def wordsAbbreviation(self, dict):
"""
:type dict: List[str]
:rtype: List[str]
"""
self.dmap = {}
self.solve(dict, 0)
return map(self.dmap.get, dict)
``````

Pingbacks已关闭。