⚡Flashcard Drill➔
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

  1. The O(n^2) pairwise check is far too slow here, so a trie is needed.
  2. Process the words in order, maintaining a trie of previously inserted words where each node counts how many words end there.
  3. For the current word w, walk down the trie; at depth d the node represents the prefix w[:d]. It contributes if w[:d] is also a suffix of w.
  4. Whether w[:d] is a suffix of w is exactly a border condition, testable in O(1) with the Z-function: w[:d] is a border iff z[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 < j requires strictly earlier words.
  • Forgetting the d == n case: the whole word is trivially a border of itself, and z[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.
🎯 Drill This Card Now➔

🧩 Related Tries Problems