Count Prefix and Suffix Pairs I

3042. Count Prefix and Suffix Pairs I

Difficulty: Easy

Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function

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 <= 50
• 1 <= words[i].length <= 10
• words[i] consists only of lowercase English letters.

Hint:

1. Iterate through all index pairs (i, j), such that i < j, and check isPrefixAndSuffix(words[i], words[j]).
2. The answer is the total number of pairs where isPrefixAndSuffix(words[i], words[j]) == true.

Solution:

We need to iterate through all index pairs (i, j) where i < j and check whether the string words[i] is both a prefix and a suffix of words[j]. For each pair, we can use PHP's built-in functions substr() to check for prefixes and suffixes.

Let's implement this solution in PHP: 3042. Count Prefix and Suffix Pairs I

  
  
  Explanation:




countPrefixAndSuffixPairs($words):


This function loops through all possible index pairs (i, j) such that i < j.
It calls isPrefixAndSuffix() to check if words[i] is both a prefix and a suffix of words[j].
If the condition is true, it increments the count.



isPrefixAndSuffix($str1, $str2):


This helper function checks whether str1 is both a prefix and a suffix of str2.
It uses substr() to extract the prefix and suffix of str2 and compares them with str1.
If both conditions are true, it returns true, otherwise, it returns false.





  
  
  Time Complexity:



The time complexity is O(n2 x m), where n is the length of the words array, and m is the average length of the strings in the array. This is due to the nested loops and the substr() operations.



  
  
  Example Output:


For the given input arrays:



["a", "aba", "ababa", "aa"] -> Output: 4


["pa", "papa", "ma", "mama"] -> Output: 2


["abab", "ab"] -> Output: 0



This solution should work efficiently within the given constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


LinkedIn
GitHub








Prefix A prefix of a string is a substring that starts from the beginning of the string and extends to any point within it. ↩



Suffix A suffix of a string is a substring that begins at any point in the string and extends to its end. ↩





          

            
  

            
        
The above is the detailed content of Count Prefix and Suffix Pairs I. For more information, please follow other related articles on the PHP Chinese website!