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精简优雅很多。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻Runtime本质(二)

1902
来自专栏天天

Airbnb JavaScript Style Guide

const foo = 1; let bar = foo; bar = 9; console.log(foo, bar); // => 1, 9

1342
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

1243
来自专栏Java3y

Java集合总结【面试题+脑图】,将知识点一网打尽!

2135
来自专栏Ryan Miao

Java String.split()用法小结

在java.lang包中有String.split()方法,返回是一个数组 我在应用中用到一些,给大家总结一下,仅供大家参考: 1、如果用“.”作为分隔的话,必...

32811
来自专栏Linyb极客之路

Java开发者易犯错误Top10

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

1124
来自专栏HelloCode开发者学习平台

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

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

1472
来自专栏java一日一条

Java HashSet工作原理及实现

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

622
来自专栏趣学算法

数据结构 第7讲 循环队列

过了一段时间,小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题,小张跑了无数次居委会,终于将挡在胡同口的建筑清除,这样住在胡同尽头的小张,就可以早...

1002
来自专栏desperate633

LintCode 单词切分题目分析

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

762

扫码关注云+社区