LeetCode 745 - Prefix and Suffix Search

The problem asks us to design a data structure that supports efficient searches based on both a prefix and a suffix. We are given an array of words, where each word has an implicit index based on its position in the array. The WordFilter class must support two operations: 1.

leetcodehardarrayhash-tablestringdesigntrie

LeetCode Problem 745

Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, Design, Trie

Solution

Problem Understanding

The problem asks us to design a data structure that supports efficient searches based on both a prefix and a suffix.

We are given an array of words, where each word has an implicit index based on its position in the array. The WordFilter class must support two operations:

  1. Initialization with the list of words.
  2. Queries of the form f(pref, suff).

For each query, we must find all words that:

  • Start with the prefix pref
  • End with the suffix suff

Among all matching words, we must return the largest index. If no word satisfies both conditions, we return -1.

The important detail is that the largest index matters. If multiple words match, we cannot simply return the first one we encounter.

The constraints strongly influence the expected solution design:

  • Up to 10^4 words
  • Each word length is at most 7
  • Up to 10^4 queries

The small maximum word length is extremely important. Although there can be many words and many queries, each word is very short. This suggests that generating combinations of prefixes and suffixes may actually be practical.

A naive implementation that scans all words for every query would require checking every word repeatedly, which becomes expensive when there are many queries.

There are several edge cases worth identifying early:

  • Multiple words may share the same prefix and suffix.
  • Duplicate words may exist at different indices.
  • Queries may match no words at all.
  • Prefix or suffix can be the entire word.
  • Prefix and suffix lengths can vary independently.
  • Because we must return the largest index, later words should overwrite earlier matches.

The problem guarantees that all strings contain only lowercase English letters and have length at least 1, which simplifies implementation because we do not need to handle empty strings.

Approaches

Brute Force Approach

The most straightforward solution is to store the words and, for every query, scan through the entire list.

For each word, we check:

  • Does it start with pref?
  • Does it end with suff?

If both conditions are true, we update the answer with the current index. Since we need the largest index, we either scan all words or scan backward from the end.

This approach is correct because it explicitly verifies every possible candidate. However, it becomes inefficient when the number of queries grows large.

Suppose there are:

  • N = 10^4 words
  • Q = 10^4 queries

Each query may scan all words, leading to approximately 10^8 checks in the worst case.

Even though each word is short, repeatedly scanning the entire dictionary is too expensive.

Key Insight

The crucial observation is that word length is extremely small, at most 7.

For a word of length L, the number of possible prefixes is L + 1, and the number of possible suffixes is also L + 1.

Since L <= 7, each word has at most:

$$8 \times 8 = 64$$

prefix-suffix combinations.

That means instead of searching during queries, we can preprocess every possible (prefix, suffix) pair and store the largest index associated with that pair.

Then each query becomes a simple hash map lookup.

For example, for "apple" we generate:

  • Prefixes: "", "a", "ap", "app", "appl", "apple"
  • Suffixes: "", "e", "le", "ple", "pple", "apple"

For every combination, we store:

(prefix + "#" + suffix) -> index

If another word later produces the same key, we overwrite the value. This automatically ensures the stored index is the largest one.

This transforms expensive query-time work into preprocessing work.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(Q × N × L) O(N) Scan all words for every query
Optimal O(N × L² + Q) O(N × L²) Precompute all prefix-suffix pairs

Here:

  • N = number of words
  • Q = number of queries
  • L = maximum word length, at most 7

Because L is tiny, the quadratic preprocessing cost is completely manageable.

Algorithm Walkthrough

Optimal Algorithm

  1. Create a hash map that maps a combined (prefix, suffix) key to the largest word index.

We use a hash map because it provides average-case O(1) lookup time. The key can be constructed as:

prefix + "#" + suffix

The separator avoids ambiguity between concatenated strings. 2. Iterate through every word along with its index.

For each word, we want to generate all possible prefix and suffix combinations. 3. Generate every possible prefix.

For a word of length L, prefixes are:

word[:0], word[:1], ..., word[:L]
  1. Generate every possible suffix.

Similarly, suffixes are:

word[L:], word[L-1:], ..., word[0:]
  1. Store every prefix-suffix combination in the hash map.

For every pair:

key = prefix + "#" + suffix

Store:

hashmap[key] = current_index

If the key already exists, overwrite it. Since indices increase as we iterate, the stored value automatically becomes the largest index. 6. During a query, construct the same combined key.

For query (pref, suff):

key = pref + "#" + suff
  1. Return the stored value if it exists.

If the key is missing, return -1.

Why it works

The algorithm works because every possible prefix-suffix combination for every word is explicitly precomputed and stored.

For any query (pref, suff), if a word exists that satisfies both conditions, then the corresponding key must already exist in the hash map. Since later indices overwrite earlier ones during preprocessing, the stored value is guaranteed to be the largest valid index.

Therefore, each query returns exactly the required answer.

Python Solution

from typing import List

class WordFilter:

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

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

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

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

                    key = prefix + "#" + suffix
                    self.lookup[key] = index

    def f(self, pref: str, suff: str) -> int:
        key = pref + "#" + suff
        return self.lookup.get(key, -1)

# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref, suff)

The implementation begins by creating a dictionary named lookup. This dictionary stores mappings from combined prefix-suffix keys to indices.

During initialization, we iterate through every word and generate all possible prefixes and suffixes.

For each combination, we create a key using:

prefix + "#" + suffix

and store the current index.

If the same combination appears later, the dictionary entry is overwritten. This naturally preserves the largest index.

The query method is extremely small because all heavy computation was already done during preprocessing. We simply build the same key and return the stored value if it exists.

Because dictionary lookups are average-case O(1), queries become very efficient.

Go Solution

type WordFilter struct {
    lookup map[string]int
}

func Constructor(words []string) WordFilter {
    lookup := make(map[string]int)

    for index, word := range words {
        length := len(word)

        for prefixLength := 0; prefixLength <= length; prefixLength++ {
            prefix := word[:prefixLength]

            for suffixStart := 0; suffixStart <= length; suffixStart++ {
                suffix := word[suffixStart:]

                key := prefix + "#" + suffix
                lookup[key] = index
            }
        }
    }

    return WordFilter{
        lookup: lookup,
    }
}

func (this *WordFilter) F(pref string, suff string) int {
    key := pref + "#" + suff

    if value, exists := this.lookup[key]; exists {
        return value
    }

    return -1
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.F(pref, suff);
 */

The Go implementation follows the same logic as the Python version.

The primary difference is that Go requires explicit map initialization using:

make(map[string]int)

Map lookups in Go return two values:

value, exists := map[key]

which allows us to distinguish between a missing key and a stored value of 0.

String slicing in Go works efficiently because strings are immutable byte slices. Since the problem guarantees lowercase English letters only, byte-based slicing is safe.

Worked Examples

Example 1

Input:

words = ["apple"]

Initialization Phase

The word "apple" has index 0.

Possible prefixes:

| Prefix |

|---|---|

| "" |

| "a" |

| "ap" |

| "app" |

| "appl" |

| "apple" |

Possible suffixes:

| Suffix |

|---|---|

| "apple" |

| "pple" |

| "ple" |

| "le" |

| "e" |

| "" |

The algorithm generates all combinations.

Some generated entries:

Key Value
"a#e" 0
"app#ple" 0
"apple#apple" 0
"ap#le" 0

Query Phase

Query:

f("a", "e")

Constructed key:

"a#e"

Lookup result:

0

Return:

0

because "apple" starts with "a" and ends with "e".

Complexity Analysis

Measure Complexity Explanation
Time O(N × L² + Q) Preprocessing generates all prefix-suffix pairs, queries are O(1)
Space O(N × L²) Hash map stores every prefix-suffix combination

Here:

  • N is the number of words
  • L is the maximum word length

For each word, we generate:

$$(L + 1)^2$$

combinations.

Since L <= 7, this is bounded by:

$$8^2 = 64$$

combinations per word, which is very manageable.

Queries require only a single hash map lookup.

Test Cases

from typing import List

class WordFilter:

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

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

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

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

                    key = prefix + "#" + suffix
                    self.lookup[key] = index

    def f(self, pref: str, suff: str) -> int:
        return self.lookup.get(pref + "#" + suff, -1)

# Provided example
wf = WordFilter(["apple"])
assert wf.f("a", "e") == 0  # basic prefix and suffix match

# No matching suffix
wf = WordFilter(["apple"])
assert wf.f("a", "x") == -1  # suffix does not exist

# No matching prefix
wf = WordFilter(["apple"])
assert wf.f("z", "e") == -1  # prefix does not exist

# Entire word as prefix and suffix
wf = WordFilter(["apple"])
assert wf.f("apple", "apple") == 0  # exact full-word match

# Multiple words, largest index should win
wf = WordFilter(["apple", "ample", "addle"])
assert wf.f("a", "le") == 2  # multiple matches, largest index returned

# Duplicate words
wf = WordFilter(["test", "test"])
assert wf.f("te", "st") == 1  # later duplicate overwrites earlier

# Single-character words
wf = WordFilter(["a", "b", "c"])
assert wf.f("a", "a") == 0  # smallest valid word

# Prefix longer than any valid candidate
wf = WordFilter(["abc"])
assert wf.f("abcd", "c") == -1  # impossible prefix

# Suffix longer than any valid candidate
wf = WordFilter(["abc"])
assert wf.f("a", "abcd") == -1  # impossible suffix

# Multiple overlapping combinations
wf = WordFilter(["banana", "bandana", "ban"])
assert wf.f("ban", "na") == 1  # bandana has largest matching index

# Query with no valid combination
wf = WordFilter(["hello", "world"])
assert wf.f("he", "ld") == -1  # no word satisfies both

Test Case Summary

Test Why
["apple"], ("a", "e") Basic functionality
("a", "x") Missing suffix
("z", "e") Missing prefix
("apple", "apple") Exact word match
Multiple matching words Ensures largest index is returned
Duplicate words Confirms overwrite behavior
Single-character words Smallest valid input
Overly long prefix Invalid query handling
Overly long suffix Invalid query handling
Overlapping matches Tests multiple valid candidates
No valid combination Ensures -1 is returned

Edge Cases

Multiple Matching Words

One subtle aspect of the problem is that multiple words may satisfy the same prefix and suffix query. A naive implementation might accidentally return the first matching index instead of the largest.

For example:

words = ["apple", "ample", "addle"]

Query:

("a", "le")

matches all three words.

The implementation handles this correctly because later indices overwrite earlier entries in the hash map during preprocessing.

Duplicate Words

The input may contain duplicate words at different indices.

For example:

["test", "test"]

Both words generate identical prefix-suffix combinations.

If the implementation avoided overwriting existing entries, it would incorrectly return index 0. Instead, the hash map stores the most recent index, ensuring the answer becomes 1.

Queries With No Match

Some queries may not correspond to any stored combination.

For example:

f("abc", "xyz")

If the implementation directly indexed into the map without checking existence, it could produce errors or incorrect default values.

Using:

dict.get(key, -1)

in Python and explicit existence checks in Go guarantees that nonexistent combinations correctly return -1.