# LeetCode 745: Prefix and Suffix Search

## Problem Restatement

We are given a list of words.

We need to design a class:

```python
WordFilter
```

that supports queries:

```python
f(prefix, suffix)
```

The query should return the largest index of a word that:

1. Starts with `prefix`
2. Ends with `suffix`

If no such word exists, return:

```python
-1
```

The official problem asks for the maximum index satisfying both prefix and suffix constraints. ([leetcode.com](https://leetcode.com/problems/prefix-and-suffix-search/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Constructor | `WordFilter(words)` |
| Query | `f(pref, suff)` |
| Output | Largest valid word index |
| No match | Return `-1` |

Example class shape:

```python
class WordFilter:

    def __init__(self, words: list[str]):
        ...

    def f(self, pref: str, suff: str) -> int:
        ...
```

## Examples

### Example 1

```python
words = ["apple"]
```

Create the object:

```python
wf = WordFilter(words)
```

Query:

```python
wf.f("a", "e")
```

The word `"apple"`:

- starts with `"a"`
- ends with `"e"`

Its index is:

```python
0
```

So the answer is:

```python
0
```

### Example 2

```python
words = ["apple", "apply", "ape"]
```

Query:

```python
wf.f("ap", "ly")
```

Only `"apply"` matches.

Its index is:

```python
1
```

So the answer is:

```python
1
```

### Example 3

```python
words = ["abc", "xbc"]
```

Query:

```python
wf.f("a", "c")
```

Only `"abc"` matches.

The answer is:

```python
0
```

## First Thought: Check Every Word

For each query:

1. Scan all words.
2. Check whether the word starts with `pref`.
3. Check whether the word ends with `suff`.
4. Keep the largest matching index.

This works, but queries can be frequent.

If there are many words and many queries, repeated scanning becomes too slow.

We should preprocess the words.

## Key Insight

The constraints are small enough that we can precompute all prefix-suffix combinations.

For every word:

```python
word
```

generate:

- every possible prefix
- every possible suffix

Then store:

```python
(prefix, suffix) -> largest index
```

Since later words have larger indices, simply overwriting the mapping automatically keeps the largest index.

This converts queries into hash map lookups.

## Algorithm

During construction:

For each word at index `i`:

1. Generate all prefixes.
2. Generate all suffixes.
3. For every `(prefix, suffix)` pair:
   - store:

```python
table[(prefix, suffix)] = i
```

During query:

```python
return table.get((pref, suff), -1)
```

## Correctness

For every word, the preprocessing step generates every possible prefix and every possible suffix of that word. Therefore, for every valid query pair `(pref, suff)` that matches the word, the mapping:

```python
(pref, suff)
```

is inserted into the table.

If multiple words match the same `(pref, suff)` pair, the algorithm overwrites the previous value with the newer index. Since words are processed in increasing index order, the final stored value is the largest matching index.

During a query, if `(pref, suff)` exists in the table, the stored value is exactly the largest index of a word having that prefix and suffix. If the pair does not exist, no word satisfies both conditions, so returning `-1` is correct.

Therefore the algorithm always returns the required answer.

## Complexity

Suppose:

```python
n = number of words
L = maximum word length
```

| Metric | Value | Why |
|---|---:|---|
| Construction time | `O(n * L^2)` | Each word has `O(L)` prefixes and `O(L)` suffixes |
| Query time | `O(1)` | Hash table lookup |
| Space | `O(n * L^2)` | Store all prefix-suffix pairs |

The official constraints make this feasible.

## Implementation

```python
class WordFilter:

    def __init__(self, words: list[str]):
        self.table = {}

        for index, word in enumerate(words):
            length = len(word)

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

                for s in range(length + 1):
                    suffix = word[length - s:]

                    self.table[(prefix, suffix)] = index

    def f(self, pref: str, suff: str) -> int:
        return self.table.get((pref, suff), -1)
```

## Code Explanation

We create a dictionary:

```python
self.table = {}
```

The keys are:

```python
(prefix, suffix)
```

The values are word indices.

For every word:

```python
for index, word in enumerate(words):
```

we generate all prefixes:

```python
for p in range(length + 1):
    prefix = word[:p]
```

and all suffixes:

```python
for s in range(length + 1):
    suffix = word[length - s:]
```

Then store the pair:

```python
self.table[(prefix, suffix)] = index
```

If another word later produces the same pair, the larger index overwrites the earlier one.

The query method is only a dictionary lookup:

```python
return self.table.get((pref, suff), -1)
```

## Testing

```python
def run_tests():
    wf = WordFilter(["apple"])

    assert wf.f("a", "e") == 0
    assert wf.f("app", "le") == 0
    assert wf.f("x", "e") == -1

    wf = WordFilter(["apple", "apply", "ape"])

    assert wf.f("ap", "ly") == 1
    assert wf.f("ap", "e") == 2
    assert wf.f("a", "e") == 2

    wf = WordFilter(["abc", "xbc"])

    assert wf.f("a", "c") == 0
    assert wf.f("x", "c") == 1
    assert wf.f("ab", "bc") == 0

    wf = WordFilter(["test", "test"])

    assert wf.f("te", "st") == 1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Single word | Basic functionality |
| Exact prefix and suffix | Standard match |
| Missing prefix | Returns `-1` |
| Multiple matching words | Largest index must win |
| Different prefixes with same suffix | Checks both constraints |
| Duplicate words | Later index overwrites earlier index |