Leetcode 648 Solution

This article provides solution to leetcode question 648 (replace-words)
Categories:
Tags:
Access this page by simply typing in "lcs 648" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/replace-words

Solution

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False

class Solution:
    def replaceWords(self, dict: List[str], sentence: str) -> str:
        root = TrieNode()

        for word in dict:
            node = root
            for ch in word:
                if not node.children[ord(ch) - 97]:
                    node.children[ord(ch) - 97] = TrieNode()
                node = node.children[ord(ch) - 97]
            else:
                node.is_word = True

        ans = []
        for word in sentence.split(' '):
            node = root
            prefix = None
            for i, ch in enumerate(word):
                if not node.children[ord(ch) - 97]:
                    break
                node = node.children[ord(ch) - 97]
                if node.is_word:
                    prefix = word[:(i + 1)]
                    break
            ans.append(word if not prefix else prefix)

        return " ".join(ans)