2023

您所在的位置：网站首页 › 后缀itous的单词 › 2023

2023

2023-05-12 12:03| 来源: 网络整理| 查看: 265

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 ( N L 2 ) O(NL^2) O(NL2)，其中 N N N 是单词数组的长度， L L L 是单词的最大长度。查找函数 F 的时间复杂度为 O ( M log ⁡ N ) O(M \log N) O(MlogN)，其中 M M M 是相应前缀和后缀所匹配到的下标集合的大小， N N N 是单词数组的长度。空间复杂度：构造函数 Constructor 的空间复杂度为 O ( N L 2 ) O(NL^2) O(NL2)，即正序和倒序两棵 Trie 树的总节点数。查找函数 F 的空间复杂度为 O ( 1 ) O(1) 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 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 return true } else if midValue r = m - 1 } } return false } func main() { wordFilter := Constructor([]string{"apple"}) ans := wordFilter.F("a", "e") fmt.Println(ans) }

2023-04-17：设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。实现 WordFilter 类： WordFilter(string[] words) 使用词典中的单词 wor_golang

rust代码如下： use std::collections::HashMap; struct WordFilter { trie: Trie, } impl WordFilter { fn new(words: Vec) -> 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, 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) }

2023-04-17：设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。实现 WordFilter 类： WordFilter(string[] words) 使用词典中的单词 wor_后缀_02

【本文地址】

2023

2023

今日新闻

推荐新闻