来源于5月”每日一题“板块中最后一天的一道题，乍一看应该是用Trie，但是实现起来有些复杂，没有其他更好的思路，然后评论区一看，又被Lee神的代码震撼到了。
TreeMap
Q: 根据输入的目标词，每输入一个字符，就从提供的词组中找出最符合规则的三个词（最多三个）。详情[戳这](Explore - LeetCode)。
A: 最大的功臣就是treemap了。首先来了解一下他的常用的、易混淆的API，如higherKey与ceilingKey的区别，前者是寻找大于当前key的key，后者是寻找大于等于当前key的key。lowerKey和floorKey同理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> res = new ArrayList<>();
TreeMap<String, Integer> map = new TreeMap<>();
Arrays.sort(products);
List<String> productList = Arrays.asList(products);
for(int i= 0; i<products.length; i++){
map.put(products[i], i);
}
String key = "";
for(char c : searchWord.toCharArray()){
key += c;
String ceiling = map.ceilingKey(key);
String floor = map.floorKey(key + "~");
if(ceiling == null || floor == null) break;
res.add(productList.subList(map.get(ceiling), Math.min(map.get(ceiling) + 3, map.get(floor) + 1)));
}
while(res.size() < searchWord.length()) res.add(new ArrayList<>());
return res;
}
|
