Python HashMap O(n) solution


  • 0
    H
    class Solution(object):
        def wordsAbbreviation(self, A):
            """
            :type dict: List[str]
            :rtype: List[str]
            """
            n= len(A)
            mp={}
            res=["" for i in range(n)]
            for i in range(n):
                word,wn=A[i],len(A[i])
                if wn<=3: 
                    mp[word]=i
                    res[i]=word
                else:
                    abbr=word[:1]+str(wn-2)+word[-1]
                    j=0
                    while mp.has_key(abbr) and mp[abbr]==-1 and j<wn:
                        abbr=word[:j+1]+str(wn-(j+1)-1)+ word[-1]
                        j+=1
                    if len(abbr)>=wn :abbr=word    
                    if mp.has_key(abbr):
                        prevword,previndex=A[mp[abbr]],mp[abbr]
                        j=0
                        while j<wn:  #they must be the same size
                            if prevword[j]==word[j]:
                                abbrbad=word[:j+1]+str(wn-(j+1)-1)+ word[-1]
                                mp[abbrbad]=-1  
                                j+=1
                            else:break
                        abbr1=prevword[:j+1]+str(wn-(j+1)-1)+prevword[-1]
                        if len(abbr1)>=wn :abbr1=prevword
                        abbr2=word[:j+1]+str(wn-(j+1)-1)+word[-1]
                        if len(abbr2)>=wn :abbr2=word
                        mp[abbr1]=previndex
                        mp[abbr2]=i
                        
                        res[mp[abbr1]]=abbr1
                        res[i]=abbr2
                    else:
                        mp[abbr]=i 
                        res[i]=abbr
            return res  
    

Log in to reply
 

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