题目描述：

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:

1. words has length in range [1, 15000].
2. For each test case, up to words.length queries WordFilter.f may be made.
3. words[i] has length in range [1, 10].
4. prefix, suffix have lengths in range [0, 10].
5. words[i] and prefix, 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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码