NeetCode #484LC-3045HardTries
← Back to All Problems#484 · #3045 · Count Prefix and Suffix Pairs II(统计前后缀下标对 II)
📌 Problem Statement & Constraints
You are given an array of strings
words. Return the number of pairs (i, j) with i < j such that words[i] is both a prefix and a suffix of words[j]. Constraints: 1 <= words.length <= 10^5, 1 <= words[i].length <= 10^5, total length at most 5 * 10^5.💡 Core Algorithmic Approaches
- The O(n^2) pairwise check is far too slow here, so a trie is needed.
- Process the words in order, maintaining a trie of previously inserted words where each node counts how many words end there.
- For the current word
w, walk down the trie; at depthdthe node represents the prefixw[:d]. It contributes ifw[:d]is also a suffix ofw. - Whether
w[:d]is a suffix ofwis exactly a border condition, testable in O(1) with the Z-function:w[:d]is a border iffz[n-d] >= d.
💻 Benchmark Python3 Implementation
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
def z_function(s: str) -> List[int]:
n = len(s)
z = [0] * n
l = r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return z
root = {}
res = 0
for w in words:
n = len(w)
z = z_function(w)
# query against previously inserted words
node = root
for d in range(1, n + 1):
ch = w[d - 1]
if ch not in node:
break # no inserted word shares this prefix
node = node[ch]
# w[:d] must also be a suffix of w
if d == n or z[n - d] >= d:
res += node.get("#", 0)
# insert w
node = root
for ch in w:
node = node.setdefault(ch, {})
node["#"] = node.get("#", 0) + 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total characters): the Z-function is linear per word and each trie walk is linear in the word length.
💾 Space Complexity
O(total characters) for the trie plus O(max word length) for the Z-array.
⚠️ Interview Pitfalls & Follow-ups
- Using the O(n^2) pairwise check: 10^5 words makes that impossible.
- Testing the border condition with a direct slice comparison:
w[:d] == w[n-d:]is O(d) per depth, giving O(L^2) per word. The Z-function makes it O(1). - Inserting before querying: a word would count itself, and
i < jrequires strictly earlier words. - Forgetting the
d == ncase: the whole word is trivially a border of itself, andz[0]is conventionally 0, so it needs a separate branch.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.