':type dict: List[str]
:type sentence: str
:rtype: str'

def replaceWords(self, dict, sentence):

    _trie = (lambda : collections.defaultdict(_trie))
    trie = _trie()
    for s in dict:
        curr = trie
        for c in s:
            curr = curr[c]
        curr.setdefault('_end')
    def replace(word):
        curr = trie
        for (i, c) in enumerate(word):
            if (c not in curr):
                break
            curr = curr[c]
            if ('_end' in curr):
                return word[:(i + 1)]
        return word
    return '    '.join(map(replace, sentence.split()))
