做一个新公司网站要多少钱,手机微信网站开发教程,临沂在线做网站,盐城做网站哪家公司好题目描述 这是 LeetCode 上的 「745. 前缀和后缀搜索」 #xff0c;难度为 「困难」。 Tag : 「字典树」 设计一个包含一些单词的特殊词典#xff0c;并能够通过前缀和后缀来检索单词。 实现 WordFilter 类#xff1a; WordFilter(string[] words) 使用词典中的单词 words 初… 题目描述 这是 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 到 ACTypeScript 耗时为原本的 ❞ Java 代码 class WordFilter { class TrieNode { TrieNode[] tns new TrieNode[26]; ListInteger 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]; } ListInteger 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]; } ListInteger 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 ArrayTrieNode() idxs: number[] new Arraynumber()}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}; vectorint 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]; } vectorint 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]; } vectorint 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(vectorstring 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 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
