【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 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.

解题思路：以输入apple为例，前缀和后缀分别有6个，分别为"","a","ap","app","appl","apple"，两者组合起来就是36个。words中最长的word的长度是10，那么组合就是11*11 = 121个，words的最大长度是15000，总的组合个数1815000，似乎在可以接受的范围之内。所以，只要预先把所有单词的所有前缀后缀的组合预先计算出来，那么查找的时间复杂度就是O(1)了。

代码如下：

class WordFilter(object):

    def __init__(self, words):

        """

        :type words: List[str]

        """

        self.dic = {}

        for i in range(len(words)-1,-1,-1):

            word = words[i]

            foward = ''

            reverse = word

            while len(reverse) >= 0:

                if (foward,reverse) not in self.dic:

                    self.dic[(foward,reverse)] = i

                for j in range(len(word)):

                    foward += word[j]

                    if (foward,reverse) not in self.dic:

                        self.dic[(foward,reverse)] = i

                if len(reverse) > 0:reverse = reverse[1:]

                else:break

                foward = ''

    def f(self, prefix, suffix):

        """

        :type prefix: str

        :type suffix: str

        :rtype: int

        """

        if (prefix,suffix) in self.dic:

            return self.dic[(prefix,suffix)]

        return -1

巴特西

【leetcode】745. Prefix and Suffix Search

最新文章

热门文章