0745. Prefix and Suffix Search ======================================================================================================================== 题目信息 -------- :题号: 0745 :难度: Hard :主题: 设计、字符串、前缀与后缀查询 :原题: `LeetCode 0745 `_ :重点: 查询必须同时满足指定前缀和后缀;多个单词匹配时返回最大的原数组下标,重复单词也按各自下标参与选择 题目重述 -------- 实现 ``WordFilter`` 类。构造函数 ``WordFilter(words)`` 接收一个小写英文单词数组,并按原数组的零基下标保存这些单词。 方法 ``f(pref, suff)`` 查找所有同时以 ``pref`` 开头、以 ``suff`` 结尾的单词。若存在一个或多个匹配项,返回其中最大的原数组下标;若没有匹配单词,返回 ``-1``。相同单词可以出现在不同下标,查询结果仍应选择最大的匹配下标。 ``words`` 的长度在 ``[1, 10^4]`` 范围内,每个单词长度在 ``[1, 7]`` 范围内;``pref`` 和 ``suff`` 的长度也都在 ``[1, 7]`` 范围内。所有字符串只含小写英文字母,``f`` 最多调用 ``10^4`` 次,同一个对象的词典在多次查询之间保持不变。 自建示例 -------- 重复单词时返回最大下标: .. code-block:: text 输入: 操作 = ["WordFilter", "f", "f", "f"] 参数 = [[ ["apple","apply","maple","apple"] ], ["ap","le"], ["app","ly"], ["ma","ly"]] 输出:[null, 3, 1, -1] 解释:前缀 "ap" 且后缀 "le" 的单词出现在下标 0 和 3,返回较大的 3;"apply" 位于下标 1;没有单词同时以 "ma" 开头并以 "ly" 结尾。 前缀和后缀可以覆盖整个单词: .. code-block:: text 输入: 操作 = ["WordFilter", "f"] 参数 = [[ ["cat","catalog"] ], ["cat","cat"]] 输出:[null, 0] 解释:单词 "cat" 同时以 "cat" 开头和结尾;"catalog" 不以 "cat" 结尾,因此唯一匹配下标是 0。