You are given a 0-indexed string array words.
Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:
isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but isPrefixAndSuffix("abc", "abcd") is false.
Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.
Example 1:
Input: words = ["a","aba","ababa","aa"]
Output: 4
Explanation: 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
Explanation: 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
Explanation: 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 <= 501 <= words[i].length <= 10words[i] consists only of lowercase English letters.Problem Overview: You are given an array of strings words. Count pairs (i, j) where i < j and words[i] appears as both a prefix and a suffix of words[j]. The task reduces to checking whether one string matches the beginning and ending segments of another string.
Approach 1: Brute Force Comparison (Time: O(n^2 * m), Space: O(1))
Check every pair of strings. For each i and j where i < j, verify whether words[j] starts with words[i] and also ends with the same string. Most languages provide direct operations like startswith and endswith, which internally compare characters one by one. If both conditions hold, increment the count.
The complexity comes from examining every pair of words (O(n^2)) and performing string comparisons up to the length of the smaller word (O(m)). This approach works well for small inputs and clearly demonstrates the core logic of the problem. It relies only on basic array iteration and simple string operations.
Approach 2: Optimized Using String Matching / Hashing (Time: O(n^2), Space: O(n * m))
You can reduce repeated character comparisons by preprocessing strings with hashing or structured string-matching techniques. Using a rolling hash or prefix hash array, compute hash values for every prefix and suffix of each string. When comparing words[i] with words[j], compare their hash values instead of characters. If the prefix hash of length len(words[i]) in words[j] matches the full hash of words[i], and the suffix hash matches as well, the pair is valid.
This turns each prefix and suffix check into an O(1) operation after preprocessing. The overall pair iteration still takes O(n^2), but individual string comparisons become constant time. Techniques like string matching and rolling hash are commonly used in competitive programming to avoid repeated scans of the same substrings.
Recommended for interviews: Start with the brute force approach. It shows you understand the problem: iterate pairs and verify prefix and suffix conditions. Once that’s clear, mention the optimization using hashing or other string-matching techniques to avoid repeated character comparisons. Interviewers typically expect the simple pair-check solution first, followed by discussion of faster substring comparison strategies.
This approach involves checking each possible pair of indices (i, j) to determine if words[i] is both a prefix and suffix of words[j]. We will simply iterate over all pairs of the words and apply the prefix and suffix condition.
This Python function counts the number of pairs (i, j) such that words[i] is both a prefix and suffix of words[j]. It defines a helper function is_prefix_and_suffix to perform this check and iterates over all pairs of the array to count the valid ones.
Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of a word.
Space Complexity: O(1) as we are using constant extra space.
An optimized approach would require reducing the number of unnecessary comparisons. Since the constraints are small, a direct approach is feasible. However, if required, we can attempt to use advanced techniques such as hashing or Rabin-Karp algorithm for prefix-suffix matching which can potentially reduce time complexity by ensuring we're not redundantly checking characters.
This optimized Python solution preprocesses each word to store all possible prefixes in a dictionary. Then for each word, it fetches potential matches from the dictionary where words are prefixes and checks them for suffix property.
Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. The improvement comes from reducing unnecessary suffix checks.
Space Complexity: O(n * m) due to storing prefixes.
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.
The time complexity is O(n^2 times m), where n and m are the length of words and the maximum length of the strings, respectively.
Python
Java
C++
Go
TypeScript
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 ith character pair of the prefix and suffix of string s.
We can use a trie to store all the character pairs, and then for each string s, we search for all the character pairs (s[i], s[m - i - 1]) in the trie, and add their counts to the answer.
The time complexity is O(n times m), and the space complexity is O(n times m). Here, n and m are the lengths of words and the maximum length of the strings, respectively.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of a word. |
| Optimized Approach Using String Matching | Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. The improvement comes from reducing unnecessary suffix checks. |
| Enumeration | — |
| Trie | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix & Suffix Check | O(n^2 * m) | O(1) | Best for understanding the problem or when constraints are small |
| Rolling Hash / String Matching Optimization | O(n^2) | O(n * m) | When repeated string comparisons are expensive and faster substring checks are needed |
Count Prefix and Suffix Pairs I & II - Leetcode 3042 & 3045 - Python • NeetCodeIO • 12,395 views views
Watch 9 more video solutions →Practice Count Prefix and Suffix Pairs I with our built-in code editor and test cases.
Practice on FleetCode