LWC 62：745. Prefix and Suffix Search
LWC 62：745. Prefix and Suffix Search
LWC 62：745. Prefix and Suffix Search
传送门：745. Prefix and Suffix Search
Problem:
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:
words has length in range [1, 15000].
For each test case, up to words.length queries WordFilter.f may be made.
words[i] has length in range [1, 10].
prefix, suffix have lengths in range [0, 10].
words[i] and prefix, suffix queries consist of lowercase letters only.
思路： 此题不看效率的话有点水，追求效率的可以考虑Trie树，此处不考虑Trie优化。简单来说，每个word都有对应的prefix和suffix，所以 对于一个word生成所有prefix和suffix的组合，并更新当前组合的权值即可。时间复杂度为O(n^2)
Java版本：
public class WordFilter {
Map<String, Integer> map;
public WordFilter(String[] words) {
map = new HashMap<>();
for (int i = 0; i < words.length; ++i) {
List<String> prefix = new ArrayList<>();
List<String> suffix = new ArrayList<>();
String word = words[i];
for (int j = 0; j <= word.length(); ++j) {
prefix.add(word.substring(0, j));
}
for (int j = word.length(); j >= 0; --j) {
suffix.add(word.substring(j));
}
for (String pre : prefix) {
for (String suf : suffix) {
if (!map.containsKey(pre + "#" + suf)) map.put(pre + "#" + suf, i);
else map.put(pre + "#" + suf, Math.max(map.get(pre + "#" + suf), i));
}
}
}
}
public int f(String prefix, String suffix) {
if (map.containsKey(prefix + "#" + suffix)) return map.get(prefix + "#" + suffix);
return -1;
}
}Python版本：
class WordFilter(object):
def __init__(self, words):
"""
:type words: List[str]
"""
self.map = {}
for index, word in enumerate(words):
prefix = ''
for char in [''] + list(word):
prefix += char
suffix = ''
for char in [''] + list(word[::-1]):
suffix += char
self.map[prefix + '#' + suffix[::-1]] = index
def f(self, prefix, suffix):
"""
:type prefix: str
:type suffix: str
:rtype: int
"""
return self.map.get(prefix + '#' + suffix, -1)不得不说，python的代码比java精简优雅很多。
腾讯云开发者
