写点什么

【LeetCode】前缀和后缀搜索 Java 题解

作者:Albert
  • 2022 年 7 月 16 日
  • 本文字数:1173 字

    阅读完需:约 4 分钟

题目描述

设计一个包含一些单词的特殊词典,并能够通过前缀和后缀来检索单词。
实现 WordFilter 类:
WordFilter(string[] words) 使用词典中的单词 words 初始化对象。f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标,返回其中 最大的下标 。如果不存在这样的单词,返回 -1 。
示例:
输入["WordFilter", "f"][[["apple"]], ["a", "e"]]输出[null, 0]解释WordFilter wordFilter = new WordFilter(["apple"]);wordFilter.f("a", "e"); // 返回 0 ,因为下标为 0 的单词:前缀 prefix = "a" 且 后缀 suff = "e" 。
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/prefix-and-suffix-search著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法题目是设计类题目,题目要求实现通过前缀和后缀来检索单词。解决查询问题,我们一般采用 hashMap 这种数据结构。采用 hashMap 解决这个问题的时候,我们先预处理,使用朴素的思想,枚举出每一种前缀和后缀,然后对应出相应的下标。在代码实践中,枚举出每一种前缀和后缀,我们通常采用 StringBuilder 的方式实现,避免字符串频繁的创建和修改。提升执行效率。具体实现代码如下,供参考。

通过代码

class WordFilter {    Map<String, Integer> map = new HashMap<>();    public WordFilter(String[] words) {         int n = words.length;        for (int i = 0; i < n; i++) {            int wordLength = words[i].length();
for (int prefixLength = 1; prefixLength <= wordLength; prefixLength++) { for (int suffixLength = 1; suffixLength <= wordLength; suffixLength++) { StringBuilder temp = new StringBuilder(); temp.append(words[i].substring(0, prefixLength)); temp.append('#'); temp.append(words[i].substring(wordLength - suffixLength)); map.put(temp.toString(), i); } } } } public int f(String pref, String suff) { StringBuilder temp = new StringBuilder(); temp.append(pref); temp.append('#'); temp.append(suff); return map.getOrDefault(temp.toString(), -1); }}
/** * Your WordFilter object will be instantiated and called as such: * WordFilter obj = new WordFilter(words); * int param_1 = obj.f(pref,suff); */
复制代码

总结

  • 本题主要考察的数据结构的灵活应用,熟练使用 hashMap 等结构,可以提升算法的执行效率。

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 3
用户头像

Albert

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】前缀和后缀搜索Java题解_LeetCode_Albert_InfoQ写作社区