leetcode 1268

这题意思是一个字母一个字母地输入单词，然后每输入一个字母，以已输入的部分作为前缀，去找符合的单词。那直接用一个map存储，key就是各种前缀，value是优先队列，用于存储products中包含该前缀的字符串，因为可以自动给字符串排序。主要性能损耗在于初始化map时维护每个优先队列的有序，而且可以想象这个map应该很大，map造好之后得到结果就容易了，直接拿就行了，注意有可能某个前缀对应的优先队列是空，即不存在该前缀开头的字符串。

这题应该也可以用trie树做。

class Solution {public List> suggestedProducts(String[] products, String searchWord) {Map> map = new HashMap<>();for(String p:products){for(int i = 1; i <= p.length(); i++){String subP = p.substring(0, i);PriorityQueue pq = map.getOrDefault(subP, new PriorityQueue<>());pq.add(p);map.put(subP, pq);}}List> ans = new ArrayList<>();for(int i = 1; i <= searchWord.length(); i++){String key = searchWord.substring(0, i);PriorityQueue pq = map.get(key);List temp = new ArrayList<>();if(null != pq) {for (int j = 0; j < 3 && !pq.isEmpty(); j++) {temp.add(pq.poll());}}ans.add(temp);}return ans;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！