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 prefix1 and a suffix2 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
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
- 1
- words[i] consists only of lowercase English letters.
Hint:
- Iterate through all index pairs (i, j), such that i
- 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
Let's implement this solution in PHP: 3042. Count Prefix and Suffix Pairs I
<?php /** * @param String[] $words * @return Integer */ function countPrefixAndSuffixPairs($words) { ... ... ... /** * go to ./solution.php */ } /** * Function to check if str1 is both a prefix and a suffix of str2 * * @param $str1 * @param $str2 * @return bool */ function isPrefixAndSuffix($str1, $str2) { ... ... ... /** * go to ./solution.php */ } // Example Test Cases $words1 = ["a", "aba", "ababa", "aa"]; $words2 = ["pa", "papa", "ma", "mama"]; $words3 = ["abab", "ab"]; echo countPrefixAndSuffixPairs($words1) . "\n"; // Output: 4 echo countPrefixAndSuffixPairs($words2) . "\n"; // Output: 2 echo countPrefixAndSuffixPairs($words3) . "\n"; // Output: 0 ?>
Explanation:
-
countPrefixAndSuffixPairs($words):
- This function loops through all possible index pairs (i, j) such that i
- 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:
- 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!

PHP remains important in modern web development, especially in content management and e-commerce platforms. 1) PHP has a rich ecosystem and strong framework support, such as Laravel and Symfony. 2) Performance optimization can be achieved through OPcache and Nginx. 3) PHP8.0 introduces JIT compiler to improve performance. 4) Cloud-native applications are deployed through Docker and Kubernetes to improve flexibility and scalability.

PHP is suitable for web development, especially in rapid development and processing dynamic content, but is not good at data science and enterprise-level applications. Compared with Python, PHP has more advantages in web development, but is not as good as Python in the field of data science; compared with Java, PHP performs worse in enterprise-level applications, but is more flexible in web development; compared with JavaScript, PHP is more concise in back-end development, but is not as good as JavaScript in front-end development.

PHP and Python each have their own advantages and are suitable for different scenarios. 1.PHP is suitable for web development and provides built-in web servers and rich function libraries. 2. Python is suitable for data science and machine learning, with concise syntax and a powerful standard library. When choosing, it should be decided based on project requirements.

PHP is a scripting language widely used on the server side, especially suitable for web development. 1.PHP can embed HTML, process HTTP requests and responses, and supports a variety of databases. 2.PHP is used to generate dynamic web content, process form data, access databases, etc., with strong community support and open source resources. 3. PHP is an interpreted language, and the execution process includes lexical analysis, grammatical analysis, compilation and execution. 4.PHP can be combined with MySQL for advanced applications such as user registration systems. 5. When debugging PHP, you can use functions such as error_reporting() and var_dump(). 6. Optimize PHP code to use caching mechanisms, optimize database queries and use built-in functions. 7

The reasons why PHP is the preferred technology stack for many websites include its ease of use, strong community support, and widespread use. 1) Easy to learn and use, suitable for beginners. 2) Have a huge developer community and rich resources. 3) Widely used in WordPress, Drupal and other platforms. 4) Integrate tightly with web servers to simplify development deployment.

PHP remains a powerful and widely used tool in modern programming, especially in the field of web development. 1) PHP is easy to use and seamlessly integrated with databases, and is the first choice for many developers. 2) It supports dynamic content generation and object-oriented programming, suitable for quickly creating and maintaining websites. 3) PHP's performance can be improved by caching and optimizing database queries, and its extensive community and rich ecosystem make it still important in today's technology stack.

In PHP, weak references are implemented through the WeakReference class and will not prevent the garbage collector from reclaiming objects. Weak references are suitable for scenarios such as caching systems and event listeners. It should be noted that it cannot guarantee the survival of objects and that garbage collection may be delayed.

The \_\_invoke method allows objects to be called like functions. 1. Define the \_\_invoke method so that the object can be called. 2. When using the $obj(...) syntax, PHP will execute the \_\_invoke method. 3. Suitable for scenarios such as logging and calculator, improving code flexibility and readability.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

Zend Studio 13.0.1
Powerful PHP integrated development environment