Prefix and Suffix Search - Practice Coding Problems

Prefix and Suffix Search - Problem

Design a special dictionary that searches words by both prefix and suffix. You need to implement the WordFilter class:

WordFilter(string[] words) - Initializes the object with the words in the dictionary.

f(string pref, string suff) - Returns the index of the word in the dictionary that has the prefix pref and the suffix suff. If there are multiple valid indices, return the largest one. If no such word exists, return -1.

Input & Output

Example 1 — Basic Prefix-Suffix Search

$ Input: words = ["apple", "application", "apply"], queries = [["ap", "e"]]

› Output: [0]

💡 Note: Only 'apple' starts with 'ap' and ends with 'e', so return its index 0

Example 2 — Multiple Matches

$ Input: words = ["cat", "bat", "rat"], queries = [["a", "t"]]

› Output: [2]

💡 Note: Both 'cat' and 'rat' start with 'a' and end with 't', but we return the largest index 2

Example 3 — No Match

$ Input: words = ["hello", "world"], queries = [["he", "d"]]

› Output: [-1]

💡 Note: No word starts with 'he' and ends with 'd', so return -1

Constraints

1 ≤ words.length ≤ 10⁴
1 ≤ words[i].length ≤ 7
1 ≤ pref.length, suff.length ≤ 7

Visualization

Tap to expand

Understanding the Visualization

Input

Dictionary: ['apple', 'application', 'apply'] | Query: prefix='ap', suffix='e'

Process

Check each word: does it start with 'ap' AND end with 'e'?

Output

Return index of matching word (largest if multiple matches)

Key Takeaway

🎯 Key Insight: Preprocess all prefix-suffix combinations for O(1) lookup time

Asked in

G Google 25 a Amazon 18 M Microsoft 12

This problem requires efficient prefix and suffix matching in a dictionary. The key insight is to preprocess the data structure during initialization for fast queries. The optimal approach uses a Trie with suffix wrapping or Hash Map with all combinations. Time: O(n×m²) preprocessing + O(1) or O(p+s) per query, Space: O(n×m²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Word	O(qnm)	O(n*m)	For each query, iterate through all words and check prefix and suffix conditions
Trie with Suffix Wrapping	O(n*m²) + O(p+s)	O(n*m²)	Use a Trie data structure with a clever suffix wrapping technique for efficient prefix-suffix search
Hash Map - Preprocess All Combinations	O(n*m²) + O(q)	O(n*m²)	Create a hash map storing all possible prefix-suffix combinations with their largest indices

Brute Force - Check Every Word — Algorithm Steps

Step 1: Store all words in an array
Step 2: For each query, iterate through all words
Step 3: Check if word starts with prefix and ends with suffix
Step 4: Track the largest valid index

Visualization

Tap to expand

Step-by-Step Walkthrough

Check apple

startsWith('ap') ✓ and endsWith('e') ✓

Check application

startsWith('ap') ✓ but endsWith('e') ✗

Result

Return index 0 (apple matches both conditions)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int startsWith(const char* word, const char* prefix) {
    return strncmp(word, prefix, strlen(prefix)) == 0;
}

int endsWith(const char* word, const char* suffix) {
    int wordLen = strlen(word);
    int suffLen = strlen(suffix);
    if (suffLen > wordLen) return 0;
    return strcmp(word + wordLen - suffLen, suffix) == 0;
}

int f(char words[][100], int wordCount, const char* pref, const char* suff) {
    int result = -1;
    for (int i = 0; i < wordCount; i++) {
        if (startsWith(words[i], pref) && endsWith(words[i], suff)) {
            result = i;
        }
    }
    return result;
}

int main() {
    char words[100][100];
    int wordCount = 3;
    strcpy(words[0], "apple");
    strcpy(words[1], "application");
    strcpy(words[2], "apply");
    
    int result = f(words, wordCount, "ap", "e");
    printf("[%d]\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q*n*m)

q queries, each checks n words, each check takes O(m) time for string comparison

✓ Linear Growth

Space Complexity

O(n*m)

Store all words in memory, total space proportional to all characters

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Word — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler