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