648. Replace Words

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

        ans = ""
        cache = {}
        for word in sentence.split(" "):
            temp = ""
            found = False
            if word in cache:
                ans += " " + cache[word]
            else:
                for char in word:
                    temp = temp + char
                    if temp in roots:
                        ans += " " + temp
                        found = True
                        cache[word] = temp
                        break

                if not found:
                    ans += " " + temp





        return ans.strip()

Using trie (prefix tree) 🎋

class TrieNode():
    def __init__(self):
        self.children = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        current = self.root

        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]

        current.end = True

    def hasRoot(self, word: str) -> bool:
        current = self.root
        temp = ""

        for char in word:
            if char not in current.children or current.end:                
                break

            temp += char
            current = current.children[char]

        return temp if current.end else False        

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        # Create trie
        trie = Trie()
        for word in dictionary:
            trie.insert(word)

        ans = ""
        for word in sentence.split(" "):
            root = trie.hasRoot(word)
            if root:
                ans += " " + root
            else:
                ans += " " + word

        return ans.strip()

More refactoring ✨

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        # Create trie
        trie = Trie()
        for word in dictionary:
            trie.insert(word)

        converted = []
        for word in sentence.split(" "):
            root = trie.getRootOrWord(word)
            converted.append(root)

        return " ".join(converted)