745. Prefix and Suffix Search

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

Design a special dictionary that searches words by prefixes and suffixes.

Implement the WordFilter class:

WordFilter(string[] words) Initializes the object with the words in the dictionary.
f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If no such word exists, return -1.

Examples:

Example 1:

Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix "a" and suffix "e".

Constraints:

1 ≤ words.length ≤ 15000
1 ≤ words[i].length ≤ 10
1 ≤ prefix.length, suffix.length ≤ 10
words[i], prefix and suffix consist of lower-case English letters only.
At most 15000 calls will be made to the function f.

Python Solution

class WordFilter:
    def __init__(self, words: List[str]):
        self.trie = {}
        for idx, word in enumerate(words):
            word = word + '#' + word
            for i in range(len(word)):
                curr = self.trie
                curr['index'] = idx
                for j in range(i, len(word)):
                    c = word[j]
                    if c not in curr:
                        curr[c] = {}
                    curr = curr[c]
                    curr['index'] = idx

    def f(self, prefix: str, suffix: str) -> int:
        curr = self.trie
        search = suffix + '#' + prefix
        
        for c in search:
            if c not in curr:
                return -1
            curr = curr[c]
            
        return curr['index']

Implementation Notes:

Uses a trie data structure to store words with their prefixes and suffixes
Time complexity: O(N * L^2) for initialization, O(P + S) for search where N is number of words, L is max word length, P is prefix length, and S is suffix length
Space complexity: O(N * L^2) for storing the trie

Java Solution

class WordFilter {
    private TrieNode root;
    
    public WordFilter(String[] words) {
        root = new TrieNode();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            String wrapped = word + "#" + word;
            for (int j = 0; j < word.length(); j++) {
                TrieNode curr = root;
                curr.index = i;
                for (int k = j; k < wrapped.length(); k++) {
                    char c = wrapped.charAt(k);
                    curr.children.putIfAbsent(c, new TrieNode());
                    curr = curr.children.get(c);
                    curr.index = i;
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        TrieNode curr = root;
        String search = suffix + "#" + prefix;
        
        for (char c : search.toCharArray()) {
            if (!curr.children.containsKey(c)) {
                return -1;
            }
            curr = curr.children.get(c);
        }
        
        return curr.index;
    }
    
    private class TrieNode {
        Map children;
        int index;
        
        TrieNode() {
            children = new HashMap<>();
            index = -1;
        }
    }
}

C++ Solution

class WordFilter {
private:
    struct TrieNode {
        unordered_map children;
        int index;
        
        TrieNode() : index(-1) {}
    };
    
    TrieNode* root;
    
public:
    WordFilter(vector& words) {
        root = new TrieNode();
        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            string wrapped = word + "#" + word;
            for (int j = 0; j < word.length(); j++) {
                TrieNode* curr = root;
                curr->index = i;
                for (int k = j; k < wrapped.length(); k++) {
                    char c = wrapped[k];
                    if (!curr->children.count(c)) {
                        curr->children[c] = new TrieNode();
                    }
                    curr = curr->children[c];
                    curr->index = i;
                }
            }
        }
    }
    
    int f(string prefix, string suffix) {
        TrieNode* curr = root;
        string search = suffix + "#" + prefix;
        
        for (char c : search) {
            if (!curr->children.count(c)) {
                return -1;
            }
            curr = curr->children[c];
        }
        
        return curr->index;
    }
};

JavaScript Solution

class WordFilter {
    constructor(words) {
        this.trie = {};
        for (let i = 0; i < words.length; i++) {
            const word = words[i];
            const wrapped = word + '#' + word;
            for (let j = 0; j < word.length; j++) {
                let curr = this.trie;
                curr.index = i;
                for (let k = j; k < wrapped.length; k++) {
                    const c = wrapped[k];
                    if (!curr[c]) {
                        curr[c] = {};
                    }
                    curr = curr[c];
                    curr.index = i;
                }
            }
        }
    }
    
    f(prefix, suffix) {
        let curr = this.trie;
        const search = suffix + '#' + prefix;
        
        for (const c of search) {
            if (!curr[c]) {
                return -1;
            }
            curr = curr[c];
        }
        
        return curr.index;
    }
}

C# Solution

public class WordFilter {
    private class TrieNode {
        public Dictionary children;
        public int index;
        
        public TrieNode() {
            children = new Dictionary();
            index = -1;
        }
    }
    
    private TrieNode root;
    
    public WordFilter(string[] words) {
        root = new TrieNode();
        for (int i = 0; i < words.Length; i++) {
            string word = words[i];
            string wrapped = word + "#" + word;
            for (int j = 0; j < word.Length; j++) {
                TrieNode curr = root;
                curr.index = i;
                for (int k = j; k < wrapped.Length; k++) {
                    char c = wrapped[k];
                    if (!curr.children.ContainsKey(c)) {
                        curr.children[c] = new TrieNode();
                    }
                    curr = curr.children[c];
                    curr.index = i;
                }
            }
        }
    }
    
    public int F(string prefix, string suffix) {
        TrieNode curr = root;
        string search = suffix + "#" + prefix;
        
        foreach (char c in search) {
            if (!curr.children.ContainsKey(c)) {
                return -1;
            }
            curr = curr.children[c];
        }
        
        return curr.index;
    }
}

Implementation Notes:

Uses a trie data structure to store words with their prefixes and suffixes
Time complexity: O(N * L^2) for initialization, O(P + S) for search where N is number of words, L is max word length, P is prefix length, and S is suffix length
Space complexity: O(N * L^2) for storing the trie