Try Python Trie :D


  • 0
    G
    class TrieNode(object):
        def __init__(self):
            self.children = {}
            self.isWord = False
            
    class Solution(object):
        def replaceWords(self, dnry, sentence):
            """
            :type dict: List[str]
            :type sentence: str
            :rtype: str
            """
            root = self.createTrie(dnry)
            res = []
            for word in sentence.split(' '):
                word, endChars = self.getEndChars(word)
                res.append(self.getRoot(root, word) + endChars)
            return ' '.join(res)
            
        def createTrie(self, words):
            root = TrieNode()
            for word in words:
                node = root
                for alp in word:
                    if alp not in node.children: node.children[alp] = TrieNode()
                    node = node.children[alp]
                node.isWord = True
            return root
        
        def getEndChars(self, word):
            end = len(word)-1
            endChars = []
            while end > 0:
                if ord(word[end]) < ord('a') or ord(word[end]) > ord('z'): endChars.insert(0, word[end])
                else: break
                end -= 1
            else: end = 0
            return word[:end+1], ''.join(endChars)
        
        def getRoot(self, tRoot, word):
            st = 0
            while st < len(word):
                alp = word[st]
                if alp not in tRoot.children: return word
                st += 1
                if tRoot.children[alp].isWord: return word[:st]
                tRoot = tRoot.children[alp]
            return word
    

Log in to reply
 

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