宫水三叶的刷题日记

V1

2022/07/14阅读:16主题:前端之巅同款

745. 前缀和后缀搜索 : 常规 Trie 运用题

题目描述

这是 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]prefsuff 仅由小写英文字母组成
  • 最多对函数 f 执行 次调用

基本分析

为了方便,我们令 wordsss,令 prefsuff 分别为 ab

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

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

暴力(TLE or 双百)

于是有了 Java 总时间超时,TypeScripe 双百的结果(应该是 TypeScript 提交不多,同时设限宽松的原因):

image.png
image.png

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 节点所对应的字符串」为 的前缀。

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

使用 Trie 优化后,JavaTLEACTypeScript 耗时为原本的

image.png
image.png

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] == nullreturn -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] == nullreturn -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] == nullreturn -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] == nullreturn -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] == nullptrreturn -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] == nullptrreturn -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 记录查询次数来进行优化)
  • 空间复杂度:

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

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

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1