Replace Words

self.word = None

Initialize the word attribute to None to mark the end of a root word.

Storing the root word at the terminal node allows quick identification of prefix matches during traversal.

node.word = word

Mark the end of the root word by storing it in the node.

This marks the node as a valid root prefix, enabling early prefix detection during search.

if node.word:

Check if the current node marks the end of a root word.

Finding a node with a stored root word indicates a valid prefix match has been found.

replacement = node.word

Update the replacement word to the found root prefix.

Replacing the original word with the shortest prefix root satisfies the problem requirement.

break

Break out of the loop after finding the shortest prefix.

Stopping traversal ensures the shortest prefix is used, preventing longer prefixes from overriding it.

self.children = {}

Initialize the children dictionary for the TrieNode.

This dictionary stores child nodes keyed by characters, enabling efficient traversal and insertion of prefixes.

node.children[c] = TrieNode()

Create a new TrieNode for the missing character.

This extends the Trie to include the new prefix path for the root word.

if c not in node.children:

Check if the current character is not a child of the current node.

If the character is missing, no prefix match exists beyond this point, so traversal stops.

break

Break out of the loop if no child node exists for the character.

Early termination prevents unnecessary traversal when no prefix match is possible.

root = TrieNode()

Create the root node of the Trie.

The root node serves as the entry point for all prefix insertions and lookups, representing an empty prefix.

if c not in node.children:

Check if the current character is not already a child of the current node.

If the character is missing, a new node must be created to represent this prefix path.

node = node.children[c]

Move to the child node corresponding to the current character.

Advancing the node pointer allows insertion or traversal to continue along the prefix path.

node = root

Start traversal from the root node for the current word.

Prefix search begins at the root of the Trie for each word to find the shortest matching root.

for c in word:

Iterate over each character in the current word.

Traverse the Trie character by character to find the shortest prefix root.

node = node.children[c]

Move to the child node corresponding to the current character.

Advancing the node pointer continues the prefix search along the Trie path.

for word in dictionary:

Iterate over each root word in the dictionary.

Each root word must be inserted into the Trie to build the prefix structure for efficient lookup.

node = root

Start traversal from the root node for the current root word.

Insertion begins at the root, moving down or creating child nodes for each character.

for c in word:

Iterate over each character in the root word.

Each character corresponds to a level in the Trie, guiding node creation or traversal.

for word in sentence.split():

Split the sentence into individual words and iterate over them.

Processing each word separately allows prefix replacement on a per-word basis.

replacement = word

Initialize replacement to the original word.

If no prefix is found, the original word remains unchanged in the result.

res.append(replacement)

Append the replacement word to the result list.

Collecting the processed words allows reconstruction of the final sentence after all replacements.

res = []

Initialize the result list to store processed words.

This list accumulates the final words after prefix replacement for efficient joining later.

return " ".join(res)

Join all words in the result list with spaces to form the final sentence.

Joining the list into a string produces the output in the required format efficiently.