💬 Discord
Sign In
NeetCode #475LC-3042EasyTries
← Back to All Problems

#475 · #3042 · Count Prefix and Suffix Pairs I(统计前后缀下标对 I)

📌 Problem Statement & Constraints

You are given a 0-indexed 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 <= 50, 1 <= words[i].length <= 10.

💡 Core Algorithmic Approaches

  1. The constraints are tiny, so the O(n^2) pairwise check is perfectly acceptable.
  2. For each pair, test startswith and endswith.
  3. Only pairs with i < j count, which the loop bounds enforce.
  4. For larger inputs, see the trie + Z-function solution in problem 3045.

💻 Benchmark Python3 Implementation

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        res = 0
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                a, b = words[i], words[j]
                if b.startswith(a) and b.endswith(a):
                    res += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2 * L): each pair costs O(L) for the two string checks.
💾 Space Complexity
O(1) beyond the input.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing a in b instead of the prefix/suffix tests: a substring match is weaker than the requirement.
  • Allowing i == j: the pair must be strictly ordered.
  • Checking only one of the two conditions: both prefix and suffix are required.
  • Assuming a is shorter than b: it must be, for b to have a as a prefix and suffix, but the checks handle it either way.