题目描述:
LeetCode 745. Prefix and Suffix Search
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
queriesWordFilter.f
may be made. words[i]
has length in range[1, 10]
.prefix, suffix
have lengths in range[0, 10]
.words[i]
andprefix, suffix
queries consist of lowercase letters only.
题目大意:
给定一组单词,按照前缀+后缀查找符合条件的单词的最大索引
解题思路:
蛮力法(Brute Force)
Python代码:
class WordFilter(object):
def __init__(self, words):
"""
:type words: List[str]
"""
self.map = {}
for idx, word in enumerate(words):
for x in range(len(word) + 1):
prefix = word[:x]
for y in range(len(word) + 1):
suffix = word[y:]
self.map[prefix + '#' + suffix] = idx
def f(self, prefix, suffix):
"""
:type prefix: str
:type suffix: str
:rtype: int
"""
return self.map.get(prefix + '#' + suffix, -1)
本文链接:http://bookshadow.com/weblog/2017/12/11/leetcode-prefix-and-suffix-search/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。