What is the time complexity of Prefix and Suffix Search?

The optimal solution has a time complexity of O(N*K^2).

What is the space complexity of Prefix and Suffix Search?

The space complexity is O(N*K^2).

What data structures are used to solve Prefix and Suffix Search?

This problem uses Array, Hash Table, String, Design, Trie. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Prefix and Suffix Search?

Insight 1: Pre-computing all possible prefix-suffix combinations is crucial for efficient searching. This avoids iterating through the entire word list for each query. Insight 2: Using a Trie data structure is an efficient way to store and search for strings based on prefixes. A modified Trie structure can be used to store combined suffix and prefix to achieve the prefix-suffix search requirement.

Which companies ask LeetCode 745. Prefix and Suffix Search in interviews?

This problem is frequently asked at Rubrik.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Prefix and Suffix Search - LeetCode 745 Solution

Prefix and Suffix Search - Complete Solution Guide

Prefix and Suffix Search is LeetCode problem 745, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Design a special dictionary that searches the words in it by a prefix and a suffix. 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, which has the prefix pref and the suffix suff . If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1 . Example 1: Input ["WordFilter", "f"] [[["apple"]], [

Detailed Explanation

The problem requires designing a `WordFilter` class that can efficiently search for words in a given dictionary based on both a prefix and a suffix. The `WordFilter` class has two methods: `__init__(words)` which initializes the dictionary with a list of words, and `f(pref, suff)` which returns the index of the word that has the given prefix `pref` and suffix `suff`. If multiple words satisfy the condition, the function should return the largest index. If no such word exists, it should return -1. The word lengths, prefix lengths, and suffix lengths are all limited to a maximum of 7 characters.

Solution Approach

The provided solutions use a Trie data structure to store all possible suffix + '#' + word combinations along with their indices. During initialization, the code iterates through each word and generates all possible suffixes. Each suffix is concatenated with '#', followed by the original word. These combined strings are then inserted into the Trie. Each Trie node stores the maximum index encountered so far for the given path. During the search (f) function, the provided suffix and prefix are combined (suffix + '#' + prefix) to form the search query. The code then traverses the Trie using the combined query. If the query exists in the Trie, the index stored at the end node (or during traversal) is returned. Otherwise, -1 is returned.

Step-by-Step Algorithm

Step 1: Initialize a Trie data structure in the `__init__` method.
Step 2: Iterate through the input `words` list with index `i`.
Step 3: For each word, generate all possible suffixes by iterating from `j = 0` to `len(word)`.
Step 4: Create a combined key: `suffix + '#' + word`.
Step 5: Insert the combined key into the Trie. During insertion, store the index `i` of the word in each node along the path.
Step 6: In the `f` method, combine the given `suff` and `pref` into a query string: `suff + '#' + pref`.
Step 7: Traverse the Trie with the query string.
Step 8: If any character in the query is not found in the Trie, return -1.
Step 9: If the entire query is found, return the index stored at the last node of the Trie (or during traversal).
Step 10: If the end of the traversal is reached but no index is present, or traversal was impossible, return -1.

Key Insights

Insight 1: Pre-computing all possible prefix-suffix combinations is crucial for efficient searching. This avoids iterating through the entire word list for each query.
Insight 2: Using a Trie data structure is an efficient way to store and search for strings based on prefixes. A modified Trie structure can be used to store combined suffix and prefix to achieve the prefix-suffix search requirement.
Insight 3: The key to solving this problem efficiently lies in creating a combined search key. The combination of suffix + '#' + prefix allows us to use a single Trie for both prefix and suffix matching.

Complexity Analysis

Time Complexity: O(N*K^2)

Space Complexity: O(N*K^2)

Topics

This problem involves: Array, Hash Table, String, Design, Trie.

Companies

Asked at: Rubrik.

Prefix and Suffix Search | LeetCode 745

Hard

Array Hash Table String Design Trie

Time: O(N*K^2)Space: O(N*K^2)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class WordFilter {

    private Map<Character, Object> trie;

    public WordFilter(String[] words) {
        trie = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int L = word.length();
            for (int j = 0; j <= L; j++) {
                String key = word.substring(j) + '#' + word;
                Map<Character, Object> node = (Map<Character, Object>) trie;
                for (char char_ : key.toCharArray()) {
                    if (!node.containsKey(char_)) {
                        node.put(char_, new HashMap<Character, Object>());
                    }
                    node = (Map<Character, Object>) node.get(char_);
                    node.put('$', i);
                }
            }
        }
    }

    public int f(String pref, String suff) {
        String query = suff + '#' + pref;
        Map<Character, Object> node = (Map<Character, Object>) trie;
        for (char char_ : query.toCharArray()) {
            if (!node.containsKey(char_)) {
                return -1;
            }
            node = (Map<Character, Object>) node.get(char_);
        }
        if (node.containsKey('$')) {
            return (int) node.get('$');
        } else {
            return -1;
        }
    }
}

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

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 745: Prefix and Suffix Search - Detailed explanation and solution approaches.

Topics

Array Hash Table String Design Trie

Companies

Rubrik

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:745

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize a Trie data structure in the `__init__` method.
2
Step 2: Iterate through the input `words` list with index `i`.
3
Step 3: For each word, generate all possible suffixes by iterating from `j = 0` to `len(word)`.
4
Step 4: Create a combined key: `suffix + '#' + word`.
5
Step 5: Insert the combined key into the Trie. During insertion, store the index `i` of the word in each node along the path.
6
Step 6: In the `f` method, combine the given `suff` and `pref` into a query string: `suff + '#' + pref`.
7
Step 7: Traverse the Trie with the query string.
8
Step 8: If any character in the query is not found in the Trie, return -1.
9
Step 9: If the entire query is found, return the index stored at the last node of the Trie (or during traversal).
10
Step 10: If the end of the traversal is reached but no index is present, or traversal was impossible, return -1.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(N*K^2)

💾

Space Complexity

O(N*K^2)

📝

Why?

The time and space complexity are dominated by the Trie construction. For each word, we create multiple strings of at most 2K length (suffix + '#' + word). The total length of these combined strings can be at most N * K * 2K. The space complexity mirrors this as the Trie will store these strings. During each `f` call we do a trie lookup for suff + '#' + pref which is bounded by K in length, giving the O(K) time complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through the list of words for each query and check if the prefix and suffix match. Keep track of the largest index that satisfies the condition.

Time: O(N*K), where N is the number of words and K is the maximum length of a word. The query `f` becomes O(N*K) since we need to check each of the N words for the required prefix and suffix. The initialization is still O(1) in time and space.Space: O(1)

Trade-offs: Brute force is simple to implement but inefficient for a large number of queries. It's preferred if the number of words is small and there are few queries. Trie based approach will shine if there are repeated f() calls.

Hash Map with Prefix and Suffix combinations

Precompute all possible prefix and suffix combinations for each word and store them in a hash map. The key would be a combination of prefix and suffix like 'prefix#suffix' and value would be the index of the word. During a query, we create combined key from prefix and suffix and check its existence in the hash map.

Time: O(N*K^2) for initialization and O(1) for query.Space: O(N*K^2)

Trade-offs: This approach can provide faster query times (O(1)) if the hash map implementation is efficient, at the cost of higher space complexity. It's suitable when fast queries are prioritized and space is not a major constraint.

✨

Key Insights

1Insight 1: Pre-computing all possible prefix-suffix combinations is crucial for efficient searching. This avoids iterating through the entire word list for each query.
2Insight 2: Using a Trie data structure is an efficient way to store and search for strings based on prefixes. A modified Trie structure can be used to store combined suffix and prefix to achieve the prefix-suffix search requirement.
3Insight 3: The key to solving this problem efficiently lies in creating a combined search key. The combination of suffix + '#' + prefix allows us to use a single Trie for both prefix and suffix matching.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty prefix or suffix. The Trie-based solution correctly handles empty prefixes and suffixes because an empty string is a valid prefix/suffix, and the '#' character ensures a clear separation between suffix and prefix.
Edge case 2: No matching word. The Trie-based solution returns -1 if the given prefix and suffix combination is not found in the Trie. This is handled correctly by checking if each character in the query exists within the Trie during traversal.
Edge case 3: Multiple matching words. The implemented Trie stores the *latest* index encountered as the words are processed. Since the words are added in order, this guarantees the *largest* index will be returned, which is what the problem asks for.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where no matching word exists. Returning an incorrect index (e.g., 0) instead of -1.

✗Common mistake 2: Not considering the edge case where the prefix or suffix is an empty string.

✗Common mistake 3: Not returning the *largest* valid index when multiple words match the criteria. Beginners may stop at the first match.

✗Common mistake 4: Incorrectly calculating the indices and substring when constructing the keys for the Trie.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Autocompletion systems where you want to suggest words based on both the beginning (prefix) and end (suffix) of the user's input. For example, suggesting filenames in a file explorer that match a certain pattern.

🏦Real-world scenario 2: Search engines where you want to find documents that contain words with specific prefixes and suffixes, useful for handling misspelled words or partial queries. For instance, finding all documents containing words that start with 'tele' and end with 'ing'.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 26, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Prefix and Suffix Search"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?