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

原创

福大大架构师每日一题

发布于 2023-04-17 14:16:50

3890

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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: 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)
}