Count Prefix and Suffix Pairs

Explanation & Solution

Description

You are given an array of strings words. A string words[i] is a prefix-suffix pair of words[j] if words[i] is both a prefix and a suffix of words[j].

Return the number of pairs (i, j) where 0 <= i < j < words.length such that words[i] is both a prefix and a suffix of words[j].

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

aba

ababa

Output: 4

Explanation: The valid pairs are:

(0, 1): "a" is a prefix and suffix of "aba"
(0, 2): "a" is a prefix and suffix of "ababa"
(0, 3): "a" is a prefix and suffix of "aa"
(1, 2): "aba" is a prefix and suffix of "ababa"

Constraints

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

Approach

Trie pattern

1. Define the Prefix-Suffix Check

Create a helper function isPrefixAndSuffix(s, t) that returns true if string s is both a prefix and a suffix of string t
First check that s is not longer than t
Use startsWith to check the prefix condition and endsWith to check the suffix condition

2. Enumerate All Valid Pairs

Use a nested loop where the outer loop picks index i and the inner loop picks index j with j > i
This ensures we only count pairs (i, j) where i < j

3. Count Matching Pairs

For each pair (i, j), check if words[i] is both a prefix and suffix of words[j]
If the condition is satisfied, increment the counter

4. Return the Count

After checking all pairs, return the total count

Key Insight

Given the small constraints (up to 50 words with length up to 10), a brute-force O(n² * L) approach with startsWith and endsWith checks is efficient and straightforward.

Time

O(n² * L) where n is the number of words and L is the max word length

Space

O(1)no extra data structures needed

Solution Code

Concatenated Words

Implement Magic Dictionary