Word Abbreviation

这题实在算法说起来很简单，实现起来的细节难度却太大了，这里只列出一些需要考虑的地方

• 一开始的原词长度小于等于3的话可以直接放进结果数组了
• 你需要一个临时栈和一个临时哈希表，前者用于存放当前轮下还存在缩写冲突的原字符串和其下标，后者用于收集所有缩写以及对应下标
• 你需要一个临时变量time来几轮这是第几轮缩写变换，因为题目要求是从字符串第二个字符开始进行缩写尝试，这个time变量可以辅助我们拿到当前词汇的缩写
• 当缩写字符数仅为1时，缩写无意义了
• 每一轮临时栈里面的数据都会被临时哈希表里面的逻辑过滤一遍，这样每次再返回临时栈里的数据规模就越来越小了

下面是根据上述逻辑细节实现的代码

class Solution(object):
    def wordsAbbreviation(self, dict):
        """
        :type dict: List[str]
        :rtype: List[str]
        """
        n = len(dict)
        res = [None] * n
        stack = []
        time = 0

        for i in xrange(n):
            if len(dict[i]) <= 3:
                res[i] = dict[i]
            else:
                stack.append([i, dict[i]])

        while stack:
            store = {}
            for index, word in stack:
                n = len(word)
                abbr = word[ : 1 + time] + str(n - 2 - time) + word[-1]
                if n - 2 - time <= 1:                    # 缩写字符长度只有1了，缩写无意义了
                    res[index] = word
                else:                                    # 缩写还有价值，继续进入哈希表
                    store.setdefault(abbr, [])
                    store[abbr].append(index)

            stack = []

            for abbr, index_lst in store.items():        
                n = len(index_lst)
                if n == 1:                               # 没有缩写冲突，可以放入res中了
                    res[index_lst[0]] = abbr
                else:
                    for i in xrange(n):                    # 还有冲突，则继续将原词和对应下标压入栈中
                        stack.append([index_lst[i], dict[index_lst[i]]])

            time += 1
        return res

这里不仅stack可以用来做遍历，用dict也是可以的

class Solution(object):
    def wordsAbbreviation(self, dict):
        """
        :type dict: List[str]
        :rtype: List[str]
        """
        n = len(dict)
        result = [0] * n
        store = collections.defaultdict(list)
        for index, word in enumerate(dict):
            store[word].append(index)

        offset = 1
        while store:
            newStore = collections.defaultdict(list)
            for word, indexList in store.iteritems():
                for index in indexList:
                    if len(dict[index]) - 2 <= offset:
                        result[index] = dict[index]
                    else:
                        newWord = dict[index][:offset] + \
                                str(len(dict[index]) - offset - 1) + \
                                dict[index][-1]
                        newStore[newWord].append(index)

            store.clear()
            for word, indexList in newStore.iteritems():
                if len(indexList) == 1:
                    result[indexList[0]] = word
                    continue
                store[word] += indexList
            offset += 1

        return result