> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Replace Words Python Solution with Tests

> Tested Python solution for LeetCode 648 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 648, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Trie](/catalog/topics/trie). [View on LeetCode](https://leetcode.com/problems/replace-words/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 648   # by problem number
lcpy gen -s replace_words   # by problem name
```

## Problem

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

### Examples

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

```
Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
```

### Constraints

* 1 \<= dictionary.length \<= 1000
* 1 \<= dictionary\[i].length \<= 100
* dictionary\[i] consists of only lower-case letters.
* 1 \<= sentence.length \<= 10^6
* sentence consists of only lower-case letters and spaces.
* The number of words in sentence is in the range \[1, 1000]
* The length of each word in sentence is in the range \[1, 1000]
* Every two consecutive words in sentence will be separated by exactly one space.
* sentence does not have leading or trailing spaces.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/replace_words/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/replace_words/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class _TrieNode:
    __slots__ = ("children", "word")

    def __init__(self) -> None:
        self.children: dict[str, _TrieNode] = {}
        self.word: str | None = None


class Solution:
    # Time: O(total chars in dictionary + total chars in sentence)
    # Space: O(total chars in dictionary)
    def replace_words(self, dictionary: list[str], sentence: str) -> str:
        root = _TrieNode()
        for entry in dictionary:
            node = root
            for char in entry:
                node = node.children.setdefault(char, _TrieNode())
            node.word = entry

        def shortest_root(word: str) -> str:
            node = root
            for char in word:
                if node.word is not None:
                    return node.word
                if char not in node.children:
                    return word
                node = node.children[char]
            return node.word if node.word is not None else word

        return " ".join(shortest_root(word) for word in sentence.split())
```

## Complexity

| Time | Space |
| - | - |
| O(total chars in dictionary + total chars in sentence) | O(total chars in dictionary) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.