Trie plus DP in Python


  • 0
    B

    We use a trie to accelerate the searching

    class Node(object):
        def __init__(self):
            self.word=0
            self.Next={}
    
    
    class Solution(object):
        
        
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: List[str]
            """
    
                
            def Init_trie():
                Root=Node()
                return Root
            
            def Insert_word(word):
                Pointer=self.Root
                for letter in word:
                    if(letter not in Pointer.Next):
                        Pointer.Next[letter]=Node()
                    Pointer=Pointer.Next[letter]
                
                Pointer.word=word   ## We store the words on the nodes
                
            
            Memo={}
            Memo['']=['']
            
            def Search(String):   ## input:string 
            		                ## Return: a list of all the possible segments by words in the wordDict 
                if String not in Memo:  
                        
                    
                    Memo[String]=[]
                    
                    Pointer=self.Root
                    
                    for letter in String:
                        if(letter in Pointer.Next):
                            Pointer=Pointer.Next[letter]
                        else:
                            break
                        
                        if Pointer.word!=0:
                            Result=Search(String[len(Pointer.word) :] )
                            for item in Result:
                                if item =='':
                                    Temp_item=Pointer.word
                                else:
                                    Temp_item=Pointer.word+' '+item
                                Memo[String].append(Temp_item)
                            
                return Memo[String]
                    
                
            
            self.Root=Init_trie()
            for word in wordDict:
                Insert_word(word)
            
    
            
            return Search(s)

Log in to reply
 

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