Python solution using hash, O(kn) solution, k supposed to be the length of the components


  • 0

    Used hash, update as proceed

    class Solution(object):
        def wordsAbbreviation(self, dict):
            m = {}
            result = []
            
            for i, w in enumerate(dict, 1):
                tail = w[-1]
                l = len(w)
                found = False
    
                head = 1
                shorten = len(w) - 2
                abbr = '{}{}{}'.format(w[:head], shorten, tail)
                
                while len(abbr) < l:
                    if abbr not in m:
                        m[abbr] = i
                        found = True
                        break
                    elif m[abbr]:
                        p = m[abbr]
                        m[abbr] = 0
                        prev = dict[p - 1]
                        prev_abbr = '{}{}{}'.format(prev[:head + 1], shorten - 1, tail)
                        if len(prev_abbr) < l:
                            result[p - 1] = prev_abbr
                            m[prev_abbr] = p
                        else:
                            result[p - 1] = prev
                            break
                    
                    head += 1
                    shorten -= 1
                    abbr = '{}{}{}'.format(w[:head], shorten, tail)
                    
                if not found:
                    abbr = w
                result.append(abbr)
            return result
    

Log in to reply
 

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