Problem statement

Build a dictionary that finds words by a given prefix and a given suffix at the same time.

Write the class WordFilter:

• WordFilter(String[] words) stores the dictionary; word i is words[i].
• int f(String pref, String suff) returns the largest index i such that words[i] starts with pref and ends with suff, or -1 if no word does. A whole word counts as its own prefix and suffix.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["WordFilter","f","f","f","f","f"]
[[["dosa","dal","salad","sad"]],["d","a"],["sa","d"],["s","lad"],["da","sa"],["dosa","dosa"]]
Output: [null,0,3,2,-1,0]
Explanation: "dosa" starts with d and ends with a. Both "salad" and "sad" fit (sa…d); the larger index, 3, wins. Only "salad" ends with "lad". No word starts with "da" and ends with "sa".

Example 2

Input: ["WordFilter","f","f"]
[[["aa","aa"]],["a","a"],["aaa","a"]]
Output: [null,1,-1]
Explanation: The same word may appear twice; the later copy has the larger index. No word is long enough to start with "aaa".

Constraints

• 1 <= words.length <= 10^4
• 1 <= words[i].length <= 7
• 1 <= pref.length, suff.length <= 7
• words[i], pref and suff consist of lowercase English letters only
• At most 10^4 calls are made to f

Hints for Prefix and Suffix Search

1. Hint 1

   Words are at most 7 letters long, so each word has at most 7 non-empty prefixes and 7 non-empty suffixes — at most 49 (prefix, suffix) pairs.

2. Hint 2

   Precompute an answer for every pair: a hash map from prefix + '#' + suffix to the index of the word. Insert the words in order so a later word overwrites an earlier one.

3. Hint 3

   A trie works too: for each word insert suffix + '{' + word for every suffix, storing the latest index in each node; a query walks suff + '{' + pref.

How to solve Prefix and Suffix Search

Because words are tiny (length ≤ 7), we can afford to list every (prefix, suffix) pair of every word in advance and map it to the largest index that has it. Each query is then one hash lookup.

Approach

1. For each word w at index i, in increasing i, and for every prefix length a and suffix length b from 1 to len(w): set map[w[0:a] + '#' + w[len-b:]] = i.
2. f(pref, suff): return map[pref + '#' + suff] if present, otherwise -1.

Why it works

A word matches the query exactly when pref is one of its prefixes and suff one of its suffixes, i.e. when the key pref#suff was generated by it. Processing indices in increasing order and overwriting leaves the largest matching index in the map. The separator # cannot occur in a word, so different (prefix, suffix) pairs never produce the same key.

Complexity

• Time — O(N · L^3) to build (N words, L ≤ 7, building each key costs O(L)); O(L) per query
• Space — O(N · L^3)

Pitfalls

• Without a separator, "ab" + "c" and "a" + "bc" collide.
• Return the largest index, so insert in order and let later words overwrite.
• A query whose prefix is longer than every word must return -1 — no special case is needed when only real prefixes are inserted.

Reference solution

Python

class WordFilter:

    def __init__(self, words: List[str]):
        self.best = {}  # "prefix#suffix" -> largest index having both
        for i, w in enumerate(words):
            n = len(w)
            for a in range(1, n + 1):
                p = w[:a]
                for b in range(1, n + 1):
                    self.best[p + "#" + w[n - b:]] = i

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

Java

class WordFilter {
    private HashMap<String, Integer> best = new HashMap<>(); // "prefix#suffix" -> largest index

    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            int n = w.length();
            for (int a = 1; a <= n; a++) {
                String p = w.substring(0, a) + "#";
                for (int b = 1; b <= n; b++) best.put(p + w.substring(n - b), i);
            }
        }
    }

    public int f(String pref, String suff) {
        return best.getOrDefault(pref + "#" + suff, -1);
    }
}

C++

class WordFilter {
    unordered_map<string, int> best; // "prefix#suffix" -> largest index having both
public:
    WordFilter(vector<string>& words) {
        for (int i = 0; i < (int)words.size(); i++) {
            const string& w = words[i];
            int n = w.size();
            for (int a = 1; a <= n; a++) {
                string p = w.substr(0, a) + "#";
                for (int b = 1; b <= n; b++) best[p + w.substr(n - b)] = i;
            }
        }
    }

    int f(string pref, string suff) {
        auto it = best.find(pref + "#" + suff);
        return it == best.end() ? -1 : it->second;
    }
};

JavaScript

var WordFilter = function(words) {
    this.best = new Map(); // "prefix#suffix" -> largest index having both
    for (var i = 0; i < words.length; i++) {
        var w = words[i], n = w.length;
        for (var a = 1; a <= n; a++) {
            var p = w.substring(0, a);
            for (var b = 1; b <= n; b++) this.best.set(p + "#" + w.substring(n - b), i);
        }
    }
};

WordFilter.prototype.f = function(pref, suff) {
    var r = this.best.get(pref + "#" + suff);
    return r === undefined ? -1 : r;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard
• Sum of Imbalance Numbers of All Subarrays Hard