2023-04-17：设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 WordFilter 类：
WordFilter(string[] words) 使用词典中的单词 words 初始化对象
f(string pref, string suff)
返回词典中具有前缀 prefix 和后缀 suff 的单词的下标
如果存在不止一个满足要求的下标，返回其中 最大的下标
如果不存在这样的单词，返回 -1 。
输入：
"WordFilter", "f"
[["apple"], "a", "e"]。
输出：
null, 0。
答案2023-04-17：
大体过程如下：
1.首先定义一个 Trie 树的结点类型 TrieNode，包含 nexts 数组和 indies 切片，其中 nexts 数组用于存储子节点，indies 切片用于存储当前节点对应的单词在原单词数组中的下标。
2.然后定义 WordFilter 结构体，包含两个指向 Trie 树根节点的指针，分别用于存储正序和倒序的 Trie 树。
3.实现 Constructor 方法，接受一个字符串数组作为参数，初始化 WordFilter 对象。在该方法内部，遍历单词数组，将每个单词插入正序和倒序的 Trie 树中。
4.实现 F 方法，接受两个字符串作为前缀和后缀参数，查找并返回满足要求的单词在原单词数组中的下标。该方法内部，分别在正序和倒序 Trie 树上匹配前缀和后缀，获取包含相应前缀和后缀的单词的下标集合。然后遍历较短的下标集合，依次在较长的下标集合中二分查找，找到最大的匹配下标。如果没有找到任何匹配，返回 -1。
5.在主函数中创建 WordFilter 对象，调用 F 方法，输出结果。
时间复杂度：
- 构造函数
Constructor的时间复杂度为 $O(NL^2)$，其中 $N$ 是单词数组的长度，$L$ 是单词的最大长度。 - 查找函数
F的时间复杂度为 $O(M log N)$，其中 $M$ 是相应前缀和后缀所匹配到的下标集合的大小，$N$ 是单词数组的长度。
空间复杂度：
- 构造函数
Constructor的空间复杂度为 $O(NL^2)$，即正序和倒序两棵 Trie 树的总节点数。 - 查找函数
F的空间复杂度为 $O(1)$，只需要常量级别的空间存储中间变量。
golang代码如下：
代码语言：go复制package main
import "fmt"
type TrieNode struct {
nexts [26]*TrieNode
indies []int
}
func NewTrieNode() *TrieNode {
return &TrieNode{
nexts: [26]*TrieNode{},
indies: []int{},
}
}
type WordFilter struct {
preHead *TrieNode
sufHead *TrieNode
}
func Constructor(words []string) WordFilter {
wf := WordFilter{
preHead: NewTrieNode(),
sufHead: NewTrieNode(),
}
for i, word := range words {
cur := wf.preHead
for _, c := range word {
path := c - 'a'
if cur.nexts[path] == nil {
cur.nexts[path] = NewTrieNode()
}
cur = cur.nexts[path]
cur.indies = append(cur.indies, i)
}
cur = wf.sufHead
for j := len(word) - 1; j >= 0; j-- {
path := word[j] - 'a'
if cur.nexts[path] == nil {
cur.nexts[path] = NewTrieNode()
}
cur = cur.nexts[path]
cur.indies = append(cur.indies, i)
}
}
return wf
}
func (this *WordFilter) F(pref string, suff string) int {
var preList, sufList []int
cur := this.preHead
for i := 0; i < len(pref) && cur != nil; i {
cur = cur.nexts[pref[i]-'a']
}
if cur != nil {
preList = cur.indies
}
if preList == nil {
return -1
}
cur = this.sufHead
for i := len(suff) - 1; i >= 0 && cur != nil; i-- {
cur = cur.nexts[suff[i]-'a']
}
if cur != nil {
sufList = cur.indies
}
if sufList == nil {
return -1
}
small, big := preList, sufList
if len(preList) > len(sufList) {
small, big = sufList, preList
}
for i := len(small) - 1; i >= 0; i-- {
if bs(big, small[i]) {
return small[i]
}
}
return -1
}
func bs(sorted []int, num int) bool {
l, r := 0, len(sorted)-1
for l <= r {
m := (l r) / 2
midValue := sorted[m]
if midValue == num {
return true
} else if midValue < num {
l = m 1
} else {
r = m - 1
}
}
return false
}
func main() {
wordFilter := Constructor([]string{"apple"})
ans := wordFilter.F("a", "e")
fmt.Println(ans)
}
rust代码如下：
代码语言：rust复制use std::collections::HashMap;
struct WordFilter {
trie: Trie,
}
impl WordFilter {
fn new(words: Vec<String>) -> Self {
let mut trie = Trie::new();
for (i, word) in words.iter().enumerate() {
let w = word.to_string() "#" word;
for j in 0..word.len() {
let mut node = &mut trie;
for c in w[j..].chars() {
node = node.children.entry(c).or_insert(Trie::new());
node.weight = i as i32;
}
}
}
Self { trie }
}
fn f(&self, pref: String, suff: String) -> i32 {
let k = suff "#" &pref;
let mut node = &self.trie;
for c in k.chars() {
if let Some(child) = node.children.get(&c) {
node = child;
} else {
return -1;
}
}
node.weight
}
}
struct Trie {
children: HashMap<char, Trie>,
weight: i32,
}
impl Trie {
fn new() -> Self {
Self {
children: HashMap::new(),
weight: 0,
}
}
}
fn main() {
let mut wordFilter = WordFilter::new(vec![String::from("apple")]);
let ans = wordFilter.f(String::from("a"), String::from("e"));
println!("ans = {}", ans)
}
