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代码如下：

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代码如下：

use std::collections::HashMap;

struct WordFilter {

    trie: Trie,
}


impl WordFilter {
    
    fn new(words: VecString>
    ) ->
 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: HashMapchar, 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)
}
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！