# LWC 62：745. Prefix and Suffix Search

## LWC 62：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.

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) {
}
for (int j = word.length(); j >= 0; --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)```

0 条评论

## 相关文章

2925

2635

2452

872

2036

### Java开发者易犯错误Top10

Arrays.asList()将返回一个数组内部是私有静态类的ArrayList，这不是java.util.ArrayList类，java.util.Array...

1184

### Java HashSet工作原理及实现

HashSet是基于HashMap来实现的，操作很简单，更像是对HashMap做了一次“封装”，而且只使用了HashMap的key来实现各种特性，我们先来感性的...

792

### BAT面试算法进阶(4)-无重复字符的最长子串

Given a string, find the length of the longest substring without repeating cha...

1852

### 数据结构-线性表|顺序表|链表(下)

1 1 1 哈喽。各位小伙伴好久不见，热心的小编赶在开学季又来给大家送上满满的干货了。祝大家开心快乐！ 继上两次咱们聊了顺序表、单链表、静态链表等知识。那么热爱...

2887

5173