LC 0648 [M] Replace Words - ALawliet/algorithms GitHub Wiki

use the first word found and make sure it is not revisited (set or first in trie)

search prefixes directly

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        rootset = set(dictionary)

        def replace(word):
            for i in range(1, len(word)):
                if word[:i] in rootset:
                    return word[:i]
            return word

        return " ".join(map(replace, sentence.split()))

trie

class Node:
    
    def __init__(self):
        self.sub = collections.defaultdict(Node)
        #here should have a isend attribute, we store the word instead.
        self.word = None
        
class Trie:
    
    def __init__(self):
        self.root = Node()
    
    def insert(self, word):
        cur = self.root
        for i in word: cur = cur.sub[i]
        cur.word = word
        
    def find(self, word):
        cur = self.root
        for i in word:
            #this means this sentence word has no 'root'
            if i not in cur.sub: return word
            cur = cur.sub[i]
            if cur.word is not None: return cur.word 
        #cannot find a matched root for current word
        return word  
        
class Solution:
    def replaceWords(self, dict: List[str], sentence: str) -> str:
        roots = Trie()
        for word in dict: roots.insert(word)
        return ' '.join(roots.find(word) for word in sentence.split())