-
Leetcode 3045. Count Prefix and Suffix Pairs II
- 1. 解题思路
- 2. 代码实现
- 题目链接：3045. Count Prefix and Suffix Pairs II
1. 解题思路
这一题的话思路上就是一个Trie树的思路来寻找前序字符，然后由于题目要求要同时满足前序和后序两个条件，因此找到每一个单词的前序子串之后再判断一下其是否同时为后序子串即可。
2. 代码实现
给出python代码实现如下：文章来源：https://www.toymoban.com/news/detail-833249.html
class Trie:
def __init__(self):
self.trie = {}
self.cnt = defaultdict(int)
def add_word(self, word):
trie = self.trie
for c in word:
trie = trie.setdefault(c, {})
trie["eos"] = word
self.cnt[word] += 1
def find(self, word):
ans = []
trie = self.trie
for c in word:
if c not in trie:
break
trie = trie[c]
if "eos" in trie:
ans.append((trie["eos"], self.cnt[trie["eos"]]))
return ans
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
trie = Trie()
ans = 0
for word in words:
s = trie.find(word)
for w, c in s:
if word.endswith(w):
ans += c
trie.add_word(word)
return ans
提交代码评测得到：耗时805ms，占用内存115.4MB。文章来源地址https://www.toymoban.com/news/detail-833249.html
到了这里，关于Leetcode 3045. Count Prefix and Suffix Pairs II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
