Python, non-trie solution (≈80ms)


  • 0
    4
    • split sentence on words
    • sort words and record their original indices
    • sort dictionary
    • with 2 pointers iterate 2 lists and substitute successors with roots if needed
    • recover sentence in original order and join to string
        def replaceWords( self, _dict, sentence ):
            
            words = sentence.split( ' ' )
            _dict = sorted( _dict )
            words_with_index = sorted( enumerate( words ), key = lambda x: x[1] )
            words_with_index = [list( j ) for j in words_with_index]    # list of tuples to list of list
            
            i = j = 0
            
            while i < len( _dict ) and j < len( words_with_index ):
                if len( _dict[i] ) <= len( words_with_index[j][1] ) and _dict[i] == words_with_index[j][1][:len(_dict[i])]:
                    words_with_index[j][1] = _dict[i]
                    j += 1
                elif _dict[i] < words_with_index[j][1]:
                    i += 1
                else:
                    j += 1
    
            return ' '.join( [ word for index, word in sorted( words_with_index, key = lambda x: x[0] )] ))
    

Log in to reply
 

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