# LeetCode 648: Replace Words

## Problem Restatement

We are given a `dictionary` of root words and a `sentence`.

A root can form a longer derivative word.

For example:

```python
root = "cat"
derivative = "cattle"
```

Since `"cattle"` starts with `"cat"`, we can replace `"cattle"` with `"cat"`.

For every word in the sentence, if it starts with one or more roots from the dictionary, replace it with the shortest matching root.

If no root matches, keep the word unchanged.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `dictionary`, a list of root words, and `sentence`, a string |
| Output | Sentence after replacing derivatives with roots |
| Rule | If multiple roots match, use the shortest root |
| Sentence format | Words are separated by one space |

Example function shape:

```python
def replaceWords(dictionary: list[str], sentence: str) -> str:
    ...
```

## Examples

Example 1:

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

Replacement:

| Word | Matching Root | Result |
|---|---|---|
| `the` | none | `the` |
| `cattle` | `cat` | `cat` |
| `was` | none | `was` |
| `rattled` | `rat` | `rat` |
| `by` | none | `by` |
| `battery` | `bat` | `bat` |

Output:

```python
"the cat was rat by the bat"
```

Example 2:

```python
dictionary = ["a", "b", "c"]
sentence = "aadsfasf absbs bbab cadsfafs"
```

Output:

```python
"a a b c"
```

Each word starts with one of the single-character roots.

## First Thought: Check Every Root

For each word in the sentence, we could check every root in the dictionary.

If the word starts with that root, keep the shortest one.

```python
class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        roots = set(dictionary)
        answer = []

        for word in sentence.split():
            replacement = word

            for i in range(1, len(word) + 1):
                prefix = word[:i]
                if prefix in roots:
                    replacement = prefix
                    break

            answer.append(replacement)

        return " ".join(answer)
```

This already works well because we check prefixes from shortest to longest.

But a trie gives a more structured prefix-search solution.

## Key Insight

We need to answer this question many times:

```text
What is the shortest dictionary root that is a prefix of this word?
```

A trie is designed for prefix lookup.

We insert every root into the trie.

Then for each sentence word, we walk through the trie character by character.

The first time we reach a node marked as a complete root, we return that root immediately.

This automatically gives the shortest matching root because we scan from left to right.

## Trie Structure

Each trie node stores:

| Field | Meaning |
|---|---|
| `children` | Map from character to next trie node |
| `word` | The complete root if this node ends a root |

For example, with roots:

```python
["cat", "bat", "rat"]
```

the trie has paths for:

```text
c -> a -> t
b -> a -> t
r -> a -> t
```

The node for `"cat"` is marked as a complete root.

## Algorithm

1. Build a trie from all roots in `dictionary`.
2. Split `sentence` into words.
3. For each word:
   1. Start at the trie root.
   2. Scan the word character by character.
   3. If the current trie node ends a root, return that root.
   4. If the next character is missing from the trie, return the original word.
   5. Otherwise, continue.
4. Join the replaced words with spaces.

## Implementation

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

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

        for word in dictionary:
            node = root

            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]

            node.word = word

        def replace(word: str) -> str:
            node = root

            for ch in word:
                if node.word is not None:
                    return node.word

                if ch not in node.children:
                    return word

                node = node.children[ch]

            if node.word is not None:
                return node.word

            return word

        words = sentence.split()
        replaced = [replace(word) for word in words]

        return " ".join(replaced)
```

## Code Explanation

First, we build the trie:

```python
root = TrieNode()
```

For every dictionary root, we create a path through the trie.

```python
for ch in word:
    if ch not in node.children:
        node.children[ch] = TrieNode()
    node = node.children[ch]
```

At the end of the root, we store the complete word:

```python
node.word = word
```

This marks the node as a root endpoint.

The replacement function walks through one sentence word:

```python
def replace(word: str) -> str:
```

Before going deeper, it checks whether the current node already ends a root:

```python
if node.word is not None:
    return node.word
```

This is what guarantees the shortest root.

If the path breaks:

```python
if ch not in node.children:
    return word
```

then no root can match this word, so we keep the original word.

At the end, we replace each word and join the result:

```python
return " ".join(replaced)
```

## Correctness

Every root in `dictionary` is inserted into the trie, and the node at the end of that root stores the root itself.

For any word in the sentence, the algorithm scans its characters from left to right. At each step, the trie path corresponds exactly to the prefix of the word scanned so far.

If the algorithm reaches a node with `word` set, then that prefix is a dictionary root. Since the scan proceeds from shortest prefix to longer prefix, this is the shortest matching root, so returning it is correct.

If the trie path breaks before reaching a root endpoint, then no dictionary root can match the word along this prefix path. Therefore, the word has no matching root and should remain unchanged.

If the scan finishes and the final node is a root endpoint, the whole word itself is a root and should be returned.

Thus every word is replaced exactly according to the problem rule, and joining the words gives the correct sentence.

## Complexity

Let:

```text
D = total number of characters in dictionary
S = total number of characters in sentence
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(D + S)` | Build the trie once, then scan sentence words |
| Space | `O(D)` | Trie stores dictionary roots |

Each sentence word is scanned only until its shortest root is found or the trie path breaks.

## Alternative Solution: Prefix Set

Because we only need the shortest prefix, a set of roots is also enough.

```python
class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        roots = set(dictionary)
        result = []

        for word in sentence.split():
            replacement = word

            for length in range(1, len(word) + 1):
                prefix = word[:length]

                if prefix in roots:
                    replacement = prefix
                    break

            result.append(replacement)

        return " ".join(result)
```

This is simpler and often fast enough.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(S * L)` in slicing cost | Prefix strings are created while checking |
| Space | `O(D)` | Stores roots in a set |

The trie avoids repeatedly constructing many prefixes.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.replaceWords(
        ["cat", "bat", "rat"],
        "the cattle was rattled by the battery",
    ) == "the cat was rat by the bat"

    assert s.replaceWords(
        ["a", "b", "c"],
        "aadsfasf absbs bbab cadsfafs",
    ) == "a a b c"

    assert s.replaceWords(
        ["c", "cat"],
        "cattle cat category",
    ) == "c c c"

    assert s.replaceWords(
        ["blue", "green"],
        "red yellow black",
    ) == "red yellow black"

    assert s.replaceWords(
        ["app", "apple"],
        "applepie apple app",
    ) == "app app app"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official-style sample | Normal replacements |
| Single-character roots | Short roots replace many words |
| Multiple matching roots | Shortest root wins |
| No matches | Words remain unchanged |
| Word equals root | Exact root is returned |