# 745. 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.
``````

``````class WordFilter {
public:
WordFilter(vector<string> words) {
for (int k = 0; k < words.size(); ++k) {
for (int i = 0; i <= words[k].size(); ++i) {
for (int j = 0; j <= words[k].size(); ++j) {
m[words[k].substr(0, i) + "#" + words[k].substr(words[k].size() - j)] = k;
}
}
}
}

int f(string prefix, string suffix) {
return (m.count(prefix + "#" + suffix)) ? m[prefix + "#" + suffix] : -1;
}

private:
unordered_map<string, int> m;
};
``````

``````class WordFilter {
public:
WordFilter(vector<string> words) {
for (int k = 0; k < words.size(); ++k) {
for (int i = 0; i <= words[k].size(); ++i) {
mp[words[k].substr(0, i)].push_back(k);
}
for (int i = 0; i <= words[k].size(); ++i) {
ms[words[k].substr(words[k].size() - i)].push_back(k);
}
}
}

int f(string prefix, string suffix) {
if (!mp.count(prefix) || !ms.count(suffix)) return -1;
vector<int> pre = mp[prefix], suf = ms[suffix];
int i = pre.size() - 1, j = suf.size() - 1;
while (i >= 0 && j >= 0) {
if (pre[i] < suf[j]) --j;
else if (pre[i] > suf[j]) --i;
else return pre[i];
}
return -1;
}

private:
unordered_map<string, vector<int>> mp, ms;
};
``````

moto72大神的帖子中还有第三种解法，但是C++中没有startsWith()和endsWith()函数，以至于无法写出C++版本的，还是Java比较叼啊。

Add and Search Word - Data structure design

https://discuss.leetcode.com/topic/113547/three-ways-to-solve-this-problem-in-java

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation