宁波公司做网站,做注册任务网站源码,域名生成器,wordpress例Leetcode 3093. Longest Common Suffix Queries 1. 解题思路2. 代码实现 题目链接#xff1a;3093. Longest Common Suffix Queries
1. 解题思路
这一题的话思路上其实就是一个Trie树的变体。
对于每一个wordsQuery当中的word#xff0c;我们要在wordsContainer当中获取答…Leetcode 3093. Longest Common Suffix Queries 1. 解题思路2. 代码实现 题目链接3093. Longest Common Suffix Queries
1. 解题思路
这一题的话思路上其实就是一个Trie树的变体。
对于每一个wordsQuery当中的word我们要在wordsContainer当中获取答案我们只需要将wordsContainer构建成一个Trie树就能够快速地获得我们所需的答案了。
具体关于Trie树的内容我们之前已经写过一个博客经典算法Trie树结构简介对其进行过介绍了这里我们就不赘述了唯一需要注意的是这里由于我们不是完全匹配单词而是匹配最长公共suffix因此我们需要做一些变体具体来说就是在trie树的每一个节点都记录下该节点对应的单词。
此外由于相同suffix的单词需要有一定的顺序关系因此我们在加入Trie树时需要对每一个节点的单词进行一下顺序的考察对此我们的处理方式是提前进行一下排序即可。
2. 代码实现
给出python代码实现如下
class Trie:def __init__(self):self.trie {}self.init -1def add_word(self, word, idx):trie self.trieif self.init -1:self.init idxfor c in word:_, trie trie.setdefault(c, (idx, {}))returndef find(self, word):trie self.trieans self.initfor c in word:if c not in trie:breakans, trie trie[c]return ansclass Solution:def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) - List[int]:words [(len(w), i, w) for i, w in enumerate(wordsContainer)]words sorted(words)trie Trie()for _, i, word in words:trie.add_word(word[::-1], i)ans [trie.find(word[::-1]) for word in wordsQuery]return ans提交代码评测得到耗时1197ms占用内存144.7MB。
