本文主要是介绍Leetcode 3093. Longest Common Suffix Queries,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 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。
这篇关于Leetcode 3093. Longest Common Suffix Queries的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!