LeetCode 745: Prefix and Suffix Search

Problem Restatement

We are given a list of words.

We need to design a class:

WordFilter

that supports queries:

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:

-1

The official problem asks for the maximum index satisfying both prefix and suffix constraints. (leetcode.com)

Input and Output

Example class shape:

class WordFilter:

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

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

Examples

Example 1

words = ["apple"]

Create the object:

wf = WordFilter(words)

Query:

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

The word "apple":

• starts with "a"
• ends with "e"

Its index is:

0

So the answer is:

0

Example 2

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

Query:

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

Only "apply" matches.

Its index is:

1

So the answer is:

1

Example 3

words = ["abc", "xbc"]

Query:

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

Only "abc" matches.

The answer is:

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:

word

generate:

• every possible prefix
• every possible suffix

Then store:

(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:

table[(prefix, suffix)] = i

During query:

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:

(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:

n = number of words
L = maximum word length

The official constraints make this feasible.

Implementation

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:

self.table = {}

The keys are:

(prefix, suffix)

The values are word indices.

For every word:

for index, word in enumerate(words):

we generate all prefixes:

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

and all suffixes:

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

Then store the pair:

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:

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

Testing

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()