3042. Count Prefix and Suffix Pairs I
Problem Description
In this problem, we're given an array of 0-indexed strings and we need to count the number of pairs of indices (i, j)
for which the string at index i
is both a prefix and a suffix of the string at index j
, and i
must be less than j
. A prefix of a string is a leading substring of the original string, while a suffix is a trailing substring.
For clarity, let's consider what constitutes a prefix and a suffix:
- A prefix of a string is the start of that string. For example, "cat" is a prefix of "cater".
- A suffix is the end of the string. For example, "ter" is a suffix of "cater".
Therefore, if a given string is both a prefix and a suffix of another, it appears at both the beginning and the end of the other string. The function isPrefixAndSuffix(str1, str2)
is supposed to return true if str1
is both a prefix and suffix of str2
, otherwise false.
The task is to count how many such distinct index pairs (i, j)
exist in the given array where i < j
.
Intuition
To solve this problem, we need to look at every possible pair of strings where the first string could be a potential prefix and suffix for the second string. We can do this through a nested loop where we iterate over each string and compare it with every other string that comes after it in the array.
When comparing the strings, we use two important string operations: startswith()
and endswith()
. These methods return true if the first string is a prefix or suffix of the second string, respectively:
- The method
startswith(s)
will check if the string under consideration starts with the substrings
. - Likewise,
endswith(s)
will verify if the string ends with the substrings
.
By ensuring that both these conditions are true for a pair of strings, we confirm that the first string is both a prefix and a suffix of the second one.
We only consider pairs where the first string index is less than the second (i < j
), to comply with the problem statement. For each such valid pair, we increment our answer. This ensures that we count all the unique pairs that satisfy the condition. The summed total gives us the desired output.
Learn more about Trie patterns.
Solution Approach
The implementation of the solution utilizes a straightforward brute force approach, where we simply iterate through every possible pair of strings and check if one string is both a prefix and a suffix of the other.
The algorithm can be described as follows:
- Initialize a counter (let's call it
ans
) and set it to 0. This will hold the count of valid pairs(i, j)
we find. - Use nested loops to iterate through the array of strings:
- The outer loop will go through each string
s
in the array, starting from the first element up to the second-to-last. We useenumerate
to get the indexi
alongside the strings
. - The inner loop will iterate through the remaining elements in the array, starting from the index
i + 1
and continuing to the end of the array. These will be the stringst
against which we will compares
.
- The outer loop will go through each string
- For each pair of strings
(s, t)
, wheres
is from the outer loop andt
is from the inner loop:- We check if string
t
starts withs
usingt.startswith(s)
. - Simultaneously, we check if string
t
ends withs
usingt.endswith(s)
. - If both conditions are
true
, meanings
is both a prefix and suffix oft
, incrementans
by 1.
- We check if string
- After the loops complete, return the count
ans
which now contains the number of index pairs(i, j)
whereisPrefixAndSuffix(words[i], words[j])
istrue
.
There are no advanced data structures utilized in this solution; it's a simple application of nested iteration over the given array and string comparison methods. The efficiency of the algorithm is not optimized; it operates with a time complexity of O(n^2 * m) where n
is the length of the words
array, and m
is the average string length.
This is because for every pair of strings, we potentially check each character up to the length of the shorter string twice (once for prefix, once for suffix).
Even though the solution is not the most optimal, it works well for small datasets and serves as a clear example of how to implement such a count conditionally on a collection of strings.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example to illustrate the solution approach. Suppose we are given the following array of strings:
1words = ["one", "oneon", "neon", "oneonne"]
We want to find the count of pairs of indices (i, j)
such that the string at index i
is both a prefix and a suffix of the string at index j
, with i < j
.
Here's how we apply the solution step by step:
- Initialize
ans
to 0. - Iterate over the array to consider every potential string
s
:- At
i = 0
,s = "one"
.- Now we compare
s
with every other stringt
with index greater thani
. - At
j = 1
,t = "oneon"
. We find thatt.startswith(s)
isTrue
butt.endswith(s)
isFalse
. Since both conditions are not met, we do not incrementans
. - At
j = 2
,t = "neon"
. Neithert.startswith(s)
nort.endswith(s)
areTrue
, so we continue. - At
j = 3
,t = "oneonne"
. Botht.startswith(s)
andt.endswith(s)
areTrue
. So, we incrementans
by 1. Now,ans = 1
.
- Now we compare
- Move to
i = 1
,s = "oneon"
. Repeat the steps, but there are no strings afters
that satisfy the conditions. - Continue to
i = 2
,s = "neon"
. There's only one string after this, and it doesn't satisfy the conditions.
- At
- No further pairs can be considered because
i
should be less thanj
, and we have exhausted all possibilities. - Finally, return the count
ans
, which in this case is1
.
Therefore, there is only 1 valid pair (0, 3)
where the first string is both a prefix and a suffix of the second string, and i
is less than j
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def count_prefix_suffix_pairs(self, words: List[str]) -> int:
5 # Initialize a variable to count the pairs
6 pair_count = 0
7
8 # Iterate through each word in the list
9 for i, source_word in enumerate(words):
10 # Compare with every other word in the list that comes after the current word
11 for target_word in words[i + 1:]:
12 # Increase the count if target_word starts and ends with source_word
13 pair_count += target_word.endswith(source_word) and target_word.startswith(source_word)
14
15 # Return the total count of pairs
16 return pair_count
17
1class Solution {
2 // Method to count the number of pairs where one word is both a prefix and a suffix of another word.
3 public int countPrefixSuffixPairs(String[] words) {
4 int pairCount = 0; // Initialize counter for pairs to 0.
5 int wordCount = words.length; // Store the length of the words array.
6
7 // Iterate over all words in the array using two nested loops to consider pairs.
8 for (int i = 0; i < wordCount; ++i) {
9 String currentWord = words[i]; // The current word for prefix/suffix checking
10
11 // Iterate over the words following the current word to avoid duplicate pairs.
12 for (int j = i + 1; j < wordCount; ++j) {
13 String comparisonWord = words[j]; // Word to compare with the current word
14
15 // Check if the comparison word starts with and ends with the current word.
16 if (comparisonWord.startsWith(currentWord) && comparisonWord.endsWith(currentWord)) {
17 pairCount++; // Increment the number of valid pairs if conditions are met.
18 }
19 }
20 }
21
22 return pairCount; // Return the final count of valid pairs.
23 }
24}
25
1class Solution {
2public:
3 // Function to count the number of pairs of strings in the given vector 'words'
4 // where one string is a prefix as well as a suffix of the other string.
5 int countPrefixSuffixPairs(vector<string>& words) {
6 int count = 0; // Initialize the count of valid pairs
7 int numWords = words.size(); // Get the number of words in the vector
8 // Iterate over each word in the vector as the potential prefix/suffix
9 for (int i = 0; i < numWords; ++i) {
10 string prefixSuffix = words[i];
11 // Iterate over the remaining words in the vector to find a match
12 for (int j = i + 1; j < numWords; ++j) {
13 string candidate = words[j];
14 // Check that the word at index i is a prefix of the word at index j
15 if (candidate.find(prefixSuffix) == 0 &&
16 // Additionally check that it is also a suffix of the word at index j
17 candidate.rfind(prefixSuffix) == candidate.length() - prefixSuffix.length()) {
18 count++; // If both prefix and suffix conditions are satisfied, increment count
19 }
20 }
21 }
22 return count; // Return the total count of valid prefix and suffix pairs
23 }
24};
25
1// Counts the number of pairs where one string in the array is both a prefix and a suffix of another string.
2// @param {string[]} words - An array of words to check for prefix-suffix pairs.
3// @returns {number} The count of prefix-suffix pairs found in the array.
4function countPrefixSuffixPairs(words: string[]): number {
5 // Initialize a variable to keep track of the count of pairs.
6 let pairCount = 0;
7
8 // Loop through each word in the array.
9 for (let i = 0; i < words.length; ++i) {
10 const word = words[i];
11
12 // Loop through the remaining words in the array starting from the next index.
13 for (const otherWord of words.slice(i + 1)) {
14 // Check if the current word is both a prefix and a suffix of the other word.
15 if (otherWord.startsWith(word) && otherWord.endsWith(word)) {
16 // Increment the count of pairs if the condition is met.
17 ++pairCount;
18 }
19 }
20 }
21
22 // Return the total count of prefix-suffix pairs.
23 return pairCount;
24}
25
Time and Space Complexity
Time Complexity
The provided function iterates over each word using a nested loop structure. The outer loop runs n
times where n
is the length of the words
list. For each iteration of the outer loop, the inner loop runs n - i - 1
times, where i
is the current index of the outer loop. There, each comparison between two strings, for startswith
and endswith
, can take up to m
operations where m
is the maximum length of the strings in the words
list. Hence, the worst-case time complexity is O(n^2 * m)
.
Space Complexity
The function mainly uses constant extra space, only storing the ans
variable and loop indices. It operates directly on the input and does not allocate additional space that depends on the input size. Therefore, the space complexity is O(1)
as it remains constant regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.