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 条评论
登录 后参与评论

相关文章

来自专栏Android点滴积累

Android辅助功能原理与基本使用详解-AccessibilityService

  辅助功能(AccessibilityService)其实是一个Android系统提供给的一种服务,本身是继承Service类的。这个服务提供了增强的用户界面...

730
来自专栏编码小白

ofbiz实体引擎(七) 检查数据源

/** * Check the datasource to make sure the entity definitions are correct,...

2604
来自专栏码匠的流水账

java9 opens与exports的区别

572
来自专栏Android学习之路

观察者模式

19810
来自专栏Android开发与分享

【Android】RxJava + Retrofit完成网络请求

33710
来自专栏技术之路

wpf listBox 多列大图片效果

修改ListBox的模版 多列大图片效果,加上删除button 看图 ? 上代码! <Window x:Class="Thunder.SetCenter.Roo...

1987
来自专栏Android点滴积累

Android辅助功能原理与基本使用详解-AccessibilityService

辅助功能原理与基本使用详解 一、辅助功能基本原理   辅助功能(AccessibilityService)其实是一个Android系统提供给的一种服务,本身是继...

3146
来自专栏大大的微笑

java如何根据二进制流确定图片的类型

 为什么需要这样做? 因为仅仅通过后缀名我们并不能得知用户是否把图片的类型更改为其他类型. public enum ImageType { PNG('P','...

2576
来自专栏积累沉淀

干货--Redis+Spring+Struts2实现网站计算器应用项目案例

有关redis的介绍我就不说了,可以参看我前几篇文章,redis快速入门 首先来看一下redis的应用场景 ? 下面是我这个项目的的运行的场景截图 ...

1886
来自专栏技术博客

设计模式之四(抽象工厂模式第二回合)

在第一回合中留下的问题,http://www.cnblogs.com/aehyok/archive/2013/05/19/3087497.html,现在就先处理...

742

扫码关注云+社区