Leetcode 648 - Replace Words with Code

The “Replace Words” problem on LeetCode is a popular problem for practising and improving your coding skills. It involves replacing each word in a given sentence with the root of the word, if it exists in a given dictionary of roots.

Here is a step-by-step guide on how to solve the “Replace Words” problem on LeetCode, including complete code examples.

Understand the problem:

The first step to solving any problem is to thoroughly understand the problem statement. In this case, the problem involves replacing each word in a given sentence with the root of the word, if it exists in a given dictionary of roots. Make sure you understand the input, output, and any constraints or limitations of the problem.

Input: dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery” Output: “the cat was rat by the bat”

Plan your solution:

Now that you understand the problem, it’s time to come up with a plan to solve it. One approach to solving this problem is to use a trie data structure to store the roots of the words in the dictionary. You can then use the trie to search for the root of each word in the sentence and replace it with the root if it exists.

Implement your solution:

Now that you have a plan, it’s time to start coding. Begin by writing a class that represents a trie node and includes a method for inserting a word into the trie. You can also write a method to search for the root of a given word in the trie. Here is an example of how to implement these methods in Python.

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_word = True
    
    def search(self, word: str) -> str:
        curr = self.root
        root_word = ""
        for ch in word:
            root_word += ch
            if ch not in curr.children:
                return ""
            curr = curr.children[ch]
            if curr.is_word:
                return root_word
        return ""

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = Trie()
        for word in dictionary:
            trie.insert(word)
        words = sentence.split()
        for i in range(len(words)):
            root_word = trie.search(words[i])
            if root_word:
                words[i] = root_word
        return " ".join(words)

Related:

• find the town judge with code
• two sum solution with code
• kth smallest element in a bst with code

Related Posts

• OA Questions, What are the optimal solution?