Given an array of n distinct non-empty strings, you need to generateminimalpossible 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.

Notice

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.

class Solution:
    """
    @param dict: an array of n distinct non-empty strings
    @return: an array of minimal possible abbreviations for every word
    """

    #thinking process

    # 1. if we enumerate the abbreviation for each word to the dictionary's word, with remaining
    #   of the words, then it is an n^2 * avg(length of the word)

    # 2. how can we optimize
    # 3, if we list down all possible abbreviation for each word in a hash, then O(n * avg(length of the word))

    # 4, can we do better ?
    # 5, two words will have the same abbreviation upuntil the common prefix and same size, 
    #   it is hard to use dictionary tree to accelerate
    # 6, also the memory usage is too huge. do we really need to store all the possible abbr for every word?
    # no, we can add all shortest level of abbr into the ans, and scan through all words, make sure all of them are unique, if not then increase the prefix for that word by one


    def wordsAbbreviation(self, dict):
        # write your code here
        if not dict:
            return dict

        abbr_map = {}
        pos = []
        ans = []
        for word in dict:
            pos.append(1)
            abbr = self.get_abbr(1, word)
            ans.append(abbr)
            abbr_map.setdefault(abbr, 0)
            abbr_map[abbr] += 1

        #print abbr_map
        is_unique = False
        while not is_unique:
            is_unique = True
            for i, word in enumerate(dict):
                cur_abbr = self.get_abbr(pos[i], word)
                if abbr_map[cur_abbr] > 1:
                    pos[i] += 1
                    next = self.get_abbr(pos[i], word)
                    ans[i] = next
                    abbr_map.setdefault(next, 0)
                    abbr_map[next] += 1
                    is_unique = False

        return ans


    def get_abbr(self, i, word):
        if i >= len(word) - 2:
            return word
        return "".join([word[0:i], str(len(word)-(i-1)-2), word[-1]])