LeetCode 745: Prefix and Suffix Search Solution

Master LeetCode problem 745 (Prefix and Suffix Search), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

745. Prefix and Suffix Search

Hard

Array Hash Table String Design Trie

Problem Explanation

Explanation:

To solve this problem efficiently, we can use a Trie data structure to store the words and then perform a search operation using both prefix and suffix. By storing reversed words in the Trie, we can easily search for suffixes. We will create a Trie for both prefix and suffix, then for each word in the input, we will insert it into both tries with the reversed word.

When searching for a word with a given prefix and suffix, we will traverse both tries simultaneously to find the longest common prefix and suffix. We will return the index of the word with the longest common prefix and suffix.

Time Complexity:

Construction of the Trie: O(N * L), where N is the number of words and L is the average length of a word.
Searching for the prefix and suffix: O(M), where M is the length of the longest common prefix and suffix.

Space Complexity:

Trie: O(N * L), where N is the number of words and L is the average length of a word.

Solution Code

class TrieNode {
    Map<Character, TrieNode> children;
    int weight;
    
    TrieNode() {
        children = new HashMap<>();
        weight = 0;
    }
}

class WordFilter {
    TrieNode prefixTrie;
    TrieNode suffixTrie;
    
    public WordFilter(String[] words) {
        prefixTrie = new TrieNode();
        suffixTrie = new TrieNode();
        
        for (int weight = 0; weight < words.length; weight++) {
            String word = words[weight];
            insertWord(word, weight);
        }
    }
    
    private void insertWord(String word, int weight) {
        String reversed = new StringBuilder(word).reverse().toString();
        insert(prefixTrie, word, weight);
        insert(suffixTrie, reversed, weight);
    }
    
    private void insert(TrieNode root, String word, int weight) {
        TrieNode node = root;
        node.weight = weight;
        
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
            node.weight = weight;
        }
    }
    
    public int f(String pref, String suff) {
        TrieNode node1 = search(prefixTrie, pref);
        TrieNode node2 = search(suffixTrie, new StringBuilder(suff).reverse().toString());
        
        if (node1 == null || node2 == null) return -1;
        
        return Math.max(node1.weight, node2.weight);
    }
    
    private TrieNode search(TrieNode root, String word) {
        TrieNode node = root;
        
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) return null;
            node = node.children.get(ch);
        }
        
        return node;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 745 (Prefix and Suffix Search)?

This page provides optimized solutions for LeetCode problem 745 (Prefix and Suffix Search) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 745 (Prefix and Suffix Search)?

The time complexity for LeetCode 745 (Prefix and Suffix Search) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 745 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 745 in Java, C++, or Python.

Back to LeetCode Solutions