#3042

Easy

LeetCode Problem Workspace

Count Prefix and Suffix Pairs I

Count all index pairs where one word is both a prefix and suffix of another, using efficient array and string checks.

array string trie rolling hash string matching

Problem Statement

Given a 0-indexed array of strings words, find the total number of pairs of indices (i, j) where i != j and words[i] is both a prefix and a suffix of words[j]. Define isPrefixAndSuffix(str1, str2) to return true if str1 is a prefix and a suffix of str2.

For example, if words = ["a","aba","ababa","aa"], the pairs that satisfy isPrefixAndSuffix are counted by checking each combination. Return the total count as an integer. Constraints: 1 <= words.length <= 50, 1 <= words[i].length <= 10, and words[i] contains only lowercase letters.

Examples

Example 1

Input: words = ["a","aba","ababa","aa"]

Output: 4

In this example, the counted index pairs are: i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true. i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true. i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true. i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true. Therefore, the answer is 4.

Example 2

Input: words = ["pa","papa","ma","mama"]

Output: 2

In this example, the counted index pairs are: i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true. i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true. Therefore, the answer is 2.

Example 3

Input: words = ["abab","ab"]

Output: 0

In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix("abab", "ab") is false. Therefore, the answer is 0.

Constraints

1 <= words.length <= 50
1 <= words[i].length <= 10
words[i] consists only of lowercase English letters.

Solution Approach

Naive Double Loop Check

Iterate over all index pairs (i, j) with i != j, and for each pair, check if words[i] is both a prefix and suffix of words[j] using simple string comparison. Increment a counter for each valid pair. This approach is direct and works well due to small input size.

Optimized String Matching

Use rolling hash or direct substring comparison to check the prefix and suffix conditions efficiently. Precompute string hashes if needed to avoid repeated slicing. This reduces the overhead when words have repeated patterns and leverages the array plus string pattern.

Trie-Based Prefix-Suffix Lookup

Build a trie storing all words for fast prefix checking and reverse trie for suffix checking. For each word, query both tries to find potential matches quickly. This method reduces redundant checks and highlights the pattern of combining array iteration with string matching structures.

Complexity Analysis

Metric	Value
Time	O(n^2 \cdot m)
Space	O(n \cdot m)

Time complexity is O(n^2 * m) because each of the n words is compared with every other word, and checking prefix and suffix takes O(m) time where m is the word length. Space complexity is O(n * m) for storing precomputed hashes or trie nodes.

What Interviewers Usually Probe

Mentions combining array iteration with string checks for prefix and suffix patterns.
Asks how to handle repeated strings efficiently in nested loops.
Looks for solutions that can leverage string structures like trie or hash maps.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude pairs where i equals j.
Checking only prefix or only suffix instead of both simultaneously.
Not accounting for overlapping prefixes and suffixes correctly when strings are identical or nested.

Follow-up variants

Count prefix-suffix pairs with variable-length substring matching instead of full word.
Extend to allow wildcards in prefix or suffix for pattern matching.
Find all pairs in larger arrays efficiently using rolling hash or trie optimizations.

FAQ

What is the core idea behind Count Prefix and Suffix Pairs I?

The core idea is to iterate over all pairs of words and count those where one word is both a prefix and a suffix of the other, leveraging array plus string techniques.

Can we use a hash map to optimize this problem?

Yes, using a hash map to store precomputed prefixes or suffixes allows faster repeated lookups and reduces redundant string comparisons.

Is a trie necessary to solve this problem?

No, a trie is optional. Nested loops with direct string checks are sufficient for small arrays, but a trie can improve efficiency for larger inputs.

What is the time complexity for checking all prefix-suffix pairs?

The time complexity is O(n^2 * m), where n is the number of words and m is the maximum word length, due to nested comparisons and string checks.

How does the array plus string pattern influence the solution?

It guides using array iteration to traverse index pairs while applying string operations like prefix and suffix checks, which is the central strategy for this problem.

terminal

Solution

Solution 1: Enumeration

We can enumerate all index pairs $(i, j)$, where $i < j$, and then determine whether `words[i]` is a prefix or suffix of `words[j]`. If it is, we increment the count.

1

2

3

4

5

6

7

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        ans = 0
        for i, s in enumerate(words):
            for t in words[i + 1 :]:
                ans += t.endswith(s) and t.startswith(s)
        return ans

Solution 2: Trie

We can treat each string $s$ in the string array as a list of character pairs, where each character pair $(s[i], s[m - i - 1])$ represents the $i$th character pair of the prefix and suffix of string $s$.

1

2

3

4

5

6

7

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        ans = 0
        for i, s in enumerate(words):
            for t in words[i + 1 :]:
                ans += t.endswith(s) and t.startswith(s)
        return ans

Continue Practicing

#3045 count prefix and suffix pairs ii #3291 minimum number of valid strings to form target i #3292 minimum number of valid strings to form target ii