【面试高频题】难度 3/5，字典树热门运用题

宫水三叶的刷题日记

发布于 2023-09-07 09:52:14

1540

发布于 2023-09-07 09:52:14

文章被收录于专栏：宫水三叶的刷题日记

题目描述

这是 LeetCode 上的「745. 前缀和后缀搜索」，难度为 「困难」。

Tag : 「字典树」

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 WordFilter 类：

WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中最大的下标。如果不存在这样的单词，返回。

示例：

输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]

输出
[null, 0]

解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。

提示：

words[i]、pref 和 suff 仅由小写英文字母组成
最多对函数 f 执行次调用

基本分析

为了方便，我们令 words 为 ss，令 pref 和 suff 分别为 a 和 b。

搜索某个前缀（后缀可看做是反方向的前缀）容易想到字典树，但单词长度数据范围只有，十分具有迷惑性，使用暴力做法最坏情况下会扫描所有的，不考虑任何的剪枝操作的话，计算量也才为，按道理是完全可以过的。

但不要忘记 LC 是一个具有「设定每个样例时长，同时又有总时长」这样奇怪机制的 OJ。

暴力（TLE or 双百)

于是有了 Java 总时间超时，TypeScripe 双百的结果（应该是 TypeScript 提交不多，同时设限宽松的原因）：

Java 代码：

class WordFilter {
    String[] ss;
    public WordFilter(String[] words) {
        ss = words;
    }
    public int f(String a, String b) {
        int n = a.length(), m = b.length();
        for (int k = ss.length - 1; k >= 0; k--) {
            String cur = ss[k];
            int len = cur.length();
            if (len < n || len < m) continue;
            boolean ok = true;
            for (int i = 0; i < n && ok; i++) {
                if (cur.charAt(i) != a.charAt(i)) ok = false;
            }
            for (int i = 0; i < m && ok; i++) {
                if (cur.charAt(len - 1 - i) != b.charAt(m - 1 - i)) ok = false;
            }
            if (ok) return k;
        }
        return -1;
    }
}

TypeScript 代码：

class WordFilter {
    ss: string[]
    constructor(words: string[]) {
        this.ss = words
    }
    f(a: string, b: string): number {
        const n = a.length, m = b.length
        for (let k = this.ss.length - 1; k >= 0; k--) {
            const cur = this.ss[k]
            const len = cur.length
            if (len < n || len < m) continue
            let ok = true
            for (let i = 0; i < n && ok; i++) {
                if (cur[i] != a[i]) ok = false
            }
            for (let i = m - 1; i >= 0; i--) {
                if (cur[len - 1 - i] != b[m - 1 - i]) ok = false
            }
            if (ok) return k
        }
        return -1
    }
}

时间复杂度：初始化操作复杂度为，检索操作复杂度为
空间复杂度：

Trie

使用字典树优化检索过程也是容易的，分别使用两棵 Trie 树来记录的前后缀，即正着存到 tr1 中，反着存到 Tr2 中。

❝还不了解 Trie 的同学可以先看前置 🧀：实现 Trie (前缀树)前置 🧀 通过图解形式讲解了 Trie 的结构与原理，以及提供了两种实现 Trie 的方式 ❞

同时对于字典树的每个节点，我们使用数组 idxs 记录经过该节点的字符串所在 ss 中的下标，若某个字典树节点的索引数组 tr.idxs 为则代表「从根节点到 tr 节点所对应的字符串」为的前缀。

这样我们可以即可在扫描前后缀 a 和 b 时，得到对应的候选下标列表 l1 和 l2，由于我们将添加到两棵 tr 中是按照下标「从小到大」进行，因此我们使用「双指针」算法分别从 l1 和 l2 结尾往后找到第一个共同元素即是答案（满足条件的最大下标）。

❝使用 Trie 优化后，Java 从 TLE 到 AC，TypeScript 耗时为原本的： ❞

Java 代码：

class WordFilter {
    class TrieNode {
        TrieNode[] tns = new TrieNode[26];
        List<Integer> idxs = new ArrayList<>();
    }
    void add(TrieNode p, String s, int idx, boolean isTurn) {
        int n = s.length();
        p.idxs.add(idx);
        for (int i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u];
            p.idxs.add(idx);
        }
    }
    int query(String a, String b) {
        int n = a.length(), m = b.length();
        TrieNode p = tr1;
        for (int i = 0; i < n; i++) {
            int u = a.charAt(i) - 'a';
            if (p.tns[u] == null) return -1;
            p = p.tns[u];
        }
        List<Integer> l1 = p.idxs;
        p = tr2;
        for (int i = m - 1; i >= 0; i--) {
            int u = b.charAt(i) - 'a';
            if (p.tns[u] == null) return -1;
            p = p.tns[u];
        }
        List<Integer> l2 = p.idxs;
        n = l1.size(); m = l2.size();
        for (int i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
            if (l1.get(i) > l2.get(j)) i--;
            else if (l1.get(i) < l2.get(j)) j--;
            else return l1.get(i);
        }
        return -1;
    }
    TrieNode tr1 = new TrieNode(), tr2 = new TrieNode();
    public WordFilter(String[] ss) {
        int n = ss.length;
        for (int i = 0; i < n; i++) {
            add(tr1, ss[i], i, false);
            add(tr2, ss[i], i, true);
        }
    }
    public int f(String a, String b) {
        return query(a, b);
    }
}

TypeScript 代码：

class TrieNode {
    tns: TrieNode[] = new Array<TrieNode>()
    idxs: number[] = new Array<number>()
}
class WordFilter {
    add(p: TrieNode, s: string, idx: number, isTurn: boolean): void {
        const n = s.length
        p.idxs.push(idx)
        for (let i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) {
            const u = s.charCodeAt(i) - 'a'.charCodeAt(0)
            if (p.tns[u] == null) p.tns[u] = new TrieNode()
            p = p.tns[u]
            p.idxs.push(idx)
        }
    }
    query(a: string, b: string): number {
        let n = a.length, m = b.length
        let p = this.tr1
        for (let i = 0; i < n; i++) {
            const u = a.charCodeAt(i) - 'a'.charCodeAt(0)
            if (p.tns[u] == null) return -1
            p = p.tns[u]
        }
        const l1 = p.idxs
        p = this.tr2
        for (let i = m - 1; i >= 0; i--) {
            const u = b.charCodeAt(i) - 'a'.charCodeAt(0)
            if (p.tns[u] == null) return -1
            p = p.tns[u]
        }
        const l2 = p.idxs
        n = l1.length; m = l2.length
        for (let i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
            if (l1[i] < l2[j]) j--
            else if (l1[i] > l2[j]) i--
            else return l1[i]
        }
        return -1
    }
    tr1: TrieNode = new TrieNode()
    tr2: TrieNode = new TrieNode()
    constructor(ss: string[]) {
        for (let i = 0; i < ss.length; i++) {
            this.add(this.tr1, ss[i], i, false)
            this.add(this.tr2, ss[i], i, true)
        }
    }
    f(a: string, b: string): number {
        return this.query(a, b)
    }
}

C++ 代码：

class WordFilter {
public:
    struct TrieNode {
        TrieNode* tns[26] {nullptr};
        vector<int> idxs;
    };
    
    void add(TrieNode* p, const string& s, int idx, bool isTurn) {
        int n = s.size();
        p->idxs.push_back(idx);
        for(int i = isTurn ? n - 1 : 0; i >= 0 && i < n; i += isTurn ? -1 : 1) {
            int u = s[i] - 'a';
            if(p->tns[u] == nullptr) p->tns[u] = new TrieNode();
            p = p->tns[u];
            p->idxs.push_back(idx);
        }
    }
    
    int query(const string& a, const string& b) {
        int n = a.size(), m = b.size();
        auto p = tr1;
        for(int i = 0; i < n; i++) {
            int u = a[i] - 'a';
            if(p->tns[u] == nullptr) return -1;
            p = p->tns[u];
        }
        vector<int>& l1 = p->idxs;
        p = tr2;
        for(int i = m - 1; i >= 0; i--) {
            int u = b[i] - 'a';
            if(p->tns[u] == nullptr) return -1;
            p = p->tns[u];
        }
        vector<int>& l2 = p->idxs;
        n = l1.size(), m = l2.size();
        for(int i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
            if(l1[i] > l2[j]) i--;
            else if(l1[i] < l2[j]) j--;
            else return l1[i];
        }
        return -1;
    }
    
    TrieNode* tr1 = new TrieNode, *tr2 = new TrieNode;
    WordFilter(vector<string>& ss) {
        int n = ss.size();
        for(int i = 0; i < n; i++) {
            add(tr1, ss[i], i, false);
            add(tr2, ss[i], i, true);
        }
    }
    
    int f(string a, string b) {
        return query(a, b);
    }
};

时间复杂度：初始化操作复杂度为，检索过程复杂度为，其中为前后缀的最大长度，为初始化数组长度，代表最多有个候选下标（注意：这里的只是粗略分析，实际上如果候选集长度越大的话，说明两个候选集是重合度是越高的，从后往前找的过程是越快结束的，可以通过方程算出一个双指针的理论最大比较次数，如果要将卡满成的话，需要将两个候选集设计成交替下标，此时 f 如果仍是次调用的话，必然会面临大量的重复查询，可通过引入 map 记录查询次数来进行优化）
空间复杂度

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除

int