745. Prefix and Suffix Search (Hard)

https://leetcode.com/problems/prefix-and-suffix-search/

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1

Note:

1. words has length in range [1, 15000].
2. For each test case, up to words.length queries WordFilter.f may be made.
3. words[i] has length in range [1, 10].
4. prefix, suffix have lengths in range [0, 10].
5. words[i] and prefix, suffix queries consist of lowercase letters only.

Solutions

class WordFilter {
    Map<String, Integer> prefixSuffixMap = new HashMap<>();

    public WordFilter(String[] words) {
        int index = 0;
        for (String word : words) {
            int len = word.length();

            String[] prefixes = new String[len + 1];
            String[] suffixes = new String[len + 1];

            prefixes[0] = "";
            suffixes[0] = "";

            // Generates the full permutations of all possible prefixes and suffixes for
            // each word. No restriction that prefixes[i] + suffixes[i] should be <= len.
            for (int i = 1; i <= len; i++) {
                prefixes[i] = prefixes[i - 1] + word.charAt(i - 1);
                suffixes[i] = word.charAt(len - i) + suffixes[i - 1];
            }

            // Concatenate the prefix and suffix as key for search when given a specific
            // query prefix and suffix
            for (String prefix : prefixes) {
                for (String suffix : suffixes) {
                    // There could be duplicates of prefix_suffix, overwrite it since larger
                    // index with larger weight are more desirable.
                    prefixSuffixMap.put(prefix + "_" + suffix, index);
                }
            }

            index++;
        }
    }

    public int f(String prefix, String suffix) {
        String key = prefix + "_" + suffix;

        if (prefixSuffixMap.containsKey(key)) {
            return prefixSuffixMap.get(key);
        }

        return -1;
    }
}

Incorrect Solutions

References