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

相关文章

来自专栏java达人

js的回调函数详解

在Javascript中,函数是第一类对象,这意味着函数可以像对象一样按照第一类管理被使用。既然函数实际上是对象:它们能被“存储”在变量中,能作为函数参数被传递...

2925
来自专栏Java3y

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

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

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

2452
来自专栏desperate633

LintCode 单词切分题目分析

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

872
来自专栏老马说编程

(49) 剖析LinkedHashMap / 计算机程序的思维逻辑

之前我们介绍了Map接口的两个实现类HashMap和TreeMap,本节来介绍另一个实现类LinkedHashMap。它是HashMap的子类,但可以保持元素按...

2036
来自专栏Linyb极客之路

Java开发者易犯错误Top10

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

1184
来自专栏java一日一条

Java HashSet工作原理及实现

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

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

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

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

1852
来自专栏数据魔术师

数据结构-线性表|顺序表|链表(下)

1 1 1 哈喽。各位小伙伴好久不见,热心的小编赶在开学季又来给大家送上满满的干货了。祝大家开心快乐! 继上两次咱们聊了顺序表、单链表、静态链表等知识。那么热爱...

2887
来自专栏闪电gogogo的专栏

【数据结构(C语言版)系列一】 线性表

数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

5173

扫码关注云+社区