3305. Count Prefix and Suffix Pairs II
My accepted Python solution to LeetCode problem 3305, Count Prefix and Suffix Pairs II, running in 1972ms.
- Difficulty: Hard
- Python
- Runtime 1972ms
- Memory 210.3MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 1972ms, memory 210.3MB, accepted 2026-01-01.
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
def isPrefixAndSuffix(str1, str2):
return str2.startswith(str1) and str2.endswith(str1)
# Use a Trie with (char, char) tuples as keys
# Build trie from front and back simultaneously
class TrieNode:
def __init__(self):
self.children = {}
self.count = 0
root = TrieNode()
result = 0
for word in words:
# Search in trie first
node = root
for i in range(len(word)):
key = (word[i], word[len(word) - 1 - i])
if key in node.children:
result += node.children[key].count
node = node.children[key]
else:
break
# Now insert the word into trie
node = root
for i in range(len(word)):
key = (word[i], word[len(word) - 1 - i])
if key not in node.children:
node.children[key] = TrieNode()
node = node.children[key]
node.count += 1
return result