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

相关文章

来自专栏蓝天

理解snprintf()函数

在编程中,需要关注snprintf()的两个问题:一是它的返回值,二是它的第二个参数。

492
来自专栏白驹过隙

Redis - set类型操作

34913
来自专栏CaiRui

Python字符串格式化

用于字符串的拼接,性能更优。 字符串格式化有两种方式:百分号方式、format方式。 百分号方式比较老,而format方式是比较先进的,企图替代古老的方式,目前...

1917
来自专栏Laoqi's Linux运维专列

匿名函数

935
来自专栏Python中文社区

Python中典型内建函数的用法

专栏作者简介 王 洪 永 在读大学生,学习过C, C++, Python, 了解java,html, javascript基础。其中就Python而言,自己写过...

1866
来自专栏Python小屋

微课系列(三):Python列表中存储的是元素的引用

技术要点:在Python中,变量不直接存储值,而是存储值的引用。同样,在列表、元组、字典、集合等容器类对象中也是存储的元素值的引用。

933
来自专栏阿凯的Excel

Python读书笔记20(函数与变量类型)

上期和大家分享了函数如何返回值。其中有个案例是实现知道边长输出正方形面积。 我们来回顾一下! ? 假如我们有一个L的列表,能否批量实现开平方的运算并赋值给新的列...

3404
来自专栏老九学堂

【干货】Java字符串之10大热点问题!

其实作为Java初学者,字符串是一个必须迈过的坎,所以老九君为了大家能够更好的掌握字符串这个知识点,以及深入的了解一些原理,搜罗总结了以下10条Java字符串的...

2624
来自专栏Java面试笔试题

Java中有几种类型的流?

字节流和字符流。字节流继承于InputStream、OutputStream,字符流继承于Reader、Writer。在java.io 包中还有许多其他的流,主...

612
来自专栏深入浅出区块链技术

智能合约语言 Solidity 教程系列5 - 数组介绍

Solidity 是以太坊智能合约编程语言,阅读本文前,你应该对以太坊、智能合约有所了解, 如果你还不了解,建议你先看以太坊是什么

923

扫码关注云+社区