# 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;
}
}
``````