题目形容

这是 LeetCode 上的 745. 前缀和后缀搜寻 ,难度为 艰难

Tag : 「字典树」

设计一个蕴含一些单词的非凡词典,并可能通过前缀和后缀来检索单词。

实现 WordFilter 类:

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

示例:

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

提醒:

  • $1 <= words.length <= 10^4$
  • $1 <= words[i].length <= 7$
  • $1 <= pref.length, suff.length <= 7$
  • words[i]prefsuff 仅由小写英文字母组成
  • 最多对函数 f 执行 $10^4$ 次调用

根本剖析

为了不便,咱们令 wordsss,令 prefsuff 别离为 ab

搜寻某个前缀(后缀可看做是反方向的前缀)容易想到字典树,但单词长度数据范畴只有 $7$,非常具备迷惑性,使用暴力做法最坏状况下会扫描所有的 $ss[i]$,不思考任何的剪枝操作的话,计算量也才为 $2 \times \ 7 \times 1e4 = 1.4 \times 10^5$,按情理是齐全能够过的。

但不要遗记 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    }}
  • 工夫复杂度:初始化操作复杂度为 $O(1)$,检索操作复杂度为 $O(\sum_{i = 0}^{n - 1} ss[i].length)$
  • 空间复杂度:$O(\sum_{i = 0}^{n - 1} ss[i].length)$

Trie

应用字典树优化检索过程也是容易的,别离应用两棵 Trie 树来记录 $ss[i]$ 的前后缀,即正着存到 tr1 中,反着存到 Tr2 中。

还不理解 Trie 的同学能够先看前置 :【设计数据结构】实现 Trie (前缀树)
前置 通过图解模式解说了 Trie 的构造与原理,以及提供了两种实现 Trie 的形式

同时对于字典树的每个节点,咱们应用数组 idxs 记录通过该节点的字符串 $ss[i]$ 所在 ss 中的下标 $i$,若某个字典树节点的索引数组 tr.idxs 为 $[a_1, a_2, ..., a_k]$ 则代表「从根节点到 tr 节点所对应的字符串」为 $ss[a_1], ss[a_2], ..., ss[a_k]$ 的前缀。

这样咱们能够即可在扫描前后缀 ab 时,失去对应的候选下标列表 l1l2,因为咱们将 $ss[i]$ 增加到两棵 tr 中是依照下标「从小到大」进行,因而咱们应用「双指针」算法别离从 l1l2 结尾往后找到第一个独特元素即是答案(满足条件的最大下标)。

应用 Trie 优化后,JavaTLEACTypeScript 耗时为本来的 $\frac{1}{7}$ :

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);    }};
  • 工夫复杂度:初始化操作复杂度为 $O(\sum_{i = 0}^{n - 1} ss[i].length)$,检索过程复杂度为 $O(a + b + n)$,其中 $a = b = 7$ 为前后缀的最大长度,$n = 1e4$ 为初始化数组长度,代表最多有 $n$ 个候选下标(留神:这里的 $n$ 只是粗略剖析,实际上如果候选集长度越大的话,阐明两个候选集是重合度是越高的,从后往前找的过程是越快完结的,能够通过方程算出一个双指针的实践最大比拟次数 $k$,如果要将 $n$ 卡满成 $1e4$ 的话,须要将两个候选集设计成交替下标,此时 f 如果仍是 $1e4$ 次调用的话,必然会面临大量的反复查问,可通过引入 map 记录查问次数来进行优化)
  • 空间复杂度:$O(\sum_{i = 0}^{n - 1} ss[i].length)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.745 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou... 。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布