Problem 745

Abstract / Summary

Design a system that can add words and check if any word in the system starts with a given prefix and ends with a given suffix.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0745.py

class WordFilter:
    def __init__(self, words: List[str]):
        self.presuf = {}

        for i, w in enumerate(words):
            # all prefixes
            for left in range(1, len(w) + 1):
                prefix = w[:left]
                if prefix not in self.presuf:
                    self.presuf[prefix] = {}

                # all suffixes
                for right in range(len(w)):
                    suffix = w[right:]
                    self.presuf[prefix][suffix] = i

    def f(self, pref: str, suff: str) -> int:
        if pref not in self.presuf:
            return -1
        if suff not in self.presuf[pref]:
            return -1

        return self.presuf[pref][suff]
23 lines | 721 bytes | submitted October 24, 2023 | GitHub   11% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 41% (200k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Design
  • Hash Table
  • String
  • Trie
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a WordFilter class that pre-computes a mapping from every possible non-empty prefix of each word to every possible suffix of the same word. The mapping stores the index of the word in the original list, allowing the f method to retrieve the highest index that matches a given prefix-suffix pair in constant time.

Initialization

During construction the code iterates over the input list words. For each word it generates all prefixes by expanding a left-hand slice from the first character up to the full word. A top-level dictionary self.presuf is created where each prefix becomes a key whose value is another dictionary.

for i, w in enumerate(words):
    for left in range(1, len(w) + 1):
        prefix = w[:left]
        if prefix not in self.presuf:
            self.presuf[prefix] = {}

Inside the same nested loop, every suffix of the current word is produced by slicing from each possible start position to the end of the word. The inner dictionary for the current prefix is then populated with the suffix as the key and the word’s index i as the value.

        for right in range(len(w)):
            suffix = w[right:]
            self.presuf[prefix][suffix] = i

Because the assignment overwrites any existing entry for the same prefix-suffix pair, the dictionary ultimately retains the largest index encountered for that combination. This behavior ensures that later words dominate earlier ones without requiring an explicit comparison.

Query Method

The f method receives a prefix pref and a suffix suff. It first checks whether the prefix exists in the outer dictionary. If the prefix is absent, the method returns -1 immediately, indicating no match.

if pref not in self.presuf:
    return -1

If the prefix is present, the method proceeds to verify the presence of the suffix within the inner dictionary associated with that prefix. Absence of the suffix also results in -1.

if suff not in self.presuf[pref]:
    return -1

When both keys are found, the stored index is returned directly.

return self.presuf[pref][suff]

Edge Cases Handled

The design naturally handles several boundary conditions:

  • Missing Prefix - When a query supplies a prefix that never appeared in any word, the early dictionary lookup fails and -1 is returned.
  • Missing Suffix - If the prefix exists but the specific suffix does not, the second lookup fails and -1 is returned.
  • Empty Strings - The construction loops start at 1 for prefixes and at 0 for suffixes, so empty strings are never inserted into the mapping. Consequently, queries with empty pref or suff are treated as missing keys and yield -1.
  • Duplicate Prefix-Suffix Pairs - When multiple words share the same prefix and suffix, later words overwrite earlier entries, guaranteeing that the returned index corresponds to the word with the greatest original position.

Performance Optimizations

The primary optimization lies in the pre-computation of a two-level hash map. By flattening the search space into a direct lookup structure, the f method avoids any runtime iteration over the word list. The inner dictionary is created only once per distinct prefix, and subsequent suffix insertions reuse the same object, reducing allocation overhead.

Another subtle optimization is the implicit “keep-latest” strategy. Because each assignment to self.presuf[prefix][suffix] replaces any prior value, the code does not need to compare indices or maintain a separate max-tracking variable. This reduces the number of conditional checks during the building phase.

Finally, the use of slice operations (w[:left] and w[right:]) leverages Python’s built-in string handling, which is implemented in C and therefore faster than manual character concatenation. The loops themselves are straightforward and avoid unnecessary intermediate data structures.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a giant magical library filled with books that have different words written on their covers. To find a book very quickly, a special filing system is built. This system looks at every single word and cuts it up like a puzzle into tiny pieces called prefixes and suffixes.

The first part of the code goes through every word and breaks it into all the bits that come at the start and all the bits that come at the end. For example, if a word is apple, it might look at a, ap, app, appl, and apple. Then it looks at the end pieces like e, le, ple, pple, and apple. It writes all these little pieces down in a big notebook. Beside each piece, it writes the number of the book where that word lives so it can be found instantly later.

When it is time to search, the code simply looks at the start piece and the end piece requested. It flips open the notebook to the page for that start piece and looks to see if the end piece is written there. If both pieces exist together in the notebook, it knows exactly which book to point to. It is a very speedy way to play a matching game with words and numbers.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 6.07 | σ = 1.56

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java
leetcode.ca C++ Java Python Go
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github black-shadows C++
charles-wangkai Java
everthis JS
fpdjsns C++
halfrost Go
JoshCrozier JS
lkwq007 Python
ruoru Rust
suxrobGM C#
varunu28 Java
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Java
leetcode.ca C++, Go, Java, Python
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fpdjsns C++
halfrost Go
JoshCrozier JavaScript
lkwq007 Python
ruoru Rust
suxrobGM C#
varunu28 Java
wisdompeak C++
27 links | 16 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

1 easy 8 medium
10 solutions   October 24, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality