Python Recursive Solution

  • 0

    After reading some solutions, I finally came up with a recursive one. The idea is almost the same as

    class Solution(object):
        def make_abbr(self, word, prefix_len):
            if prefix_len >= len(word) - 2:
                return word
            return word[:prefix_len] + str(len(word[prefix_len:-1])) + word[-1]
        def helper(self, result, words, index_list, prefix_len):
            table = collections.defaultdict(list)
            for index in index_list:    # group words by their abbreviations. Key: abbreviation, value: list of word indexes
                abbr = self.make_abbr(words[index], prefix_len)
            for abbr, group in table.items():
                if len(group) == 1:    # base case, no duplicate abbreviations
                    result[group[0]] = abbr
                else:    # if some words has the same abbreviations, increase the prefix length
                    self.helper(result, words, group, prefix_len + 1)
        def wordsAbbreviation(self, dict):
            :type dict: List[str]
            :rtype: List[str]
            result = [None] * len(dict)
            self.helper(result, dict, range(len(dict)), 1)
            return result

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.