题目描述：

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.

题目大意：

给定n个不重复的非空字符串，你需要按照如下规则为每个字符串生成其最短缩写。

缩写由首字母开始、末字母结束，中间包含被缩略的字符。

同一个缩写不能对应两个不同的单词。

如果缩写没有使单词变短，就保持原样。

注意：

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

解题思路：

字典（Map）+递归

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

尝试将所有字符串从最短长度开始进行压缩

若同一个压缩字符串对应多个原串，则将这些串递归求解

否则，将该压缩串的结果加入dmap

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)

 

本文链接：http://bookshadow.com/weblog/2017/03/12/leetcode-word-abbreviation/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码