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 and Python each have their own advantages, and the choice should be based on project requirements. 1.PHP is suitable for web development, with simple syntax and high execution efficiency. 2. Python is suitable for data science and machine learning, with concise syntax and rich libraries.

PHP is not dying, but constantly adapting and evolving. 1) PHP has undergone multiple version iterations since 1994 to adapt to new technology trends. 2) It is currently widely used in e-commerce, content management systems and other fields. 3) PHP8 introduces JIT compiler and other functions to improve performance and modernization. 4) Use OPcache and follow PSR-12 standards to optimize performance and code quality.

The future of PHP will be achieved by adapting to new technology trends and introducing innovative features: 1) Adapting to cloud computing, containerization and microservice architectures, supporting Docker and Kubernetes; 2) introducing JIT compilers and enumeration types to improve performance and data processing efficiency; 3) Continuously optimize performance and promote best practices.

In PHP, trait is suitable for situations where method reuse is required but not suitable for inheritance. 1) Trait allows multiplexing methods in classes to avoid multiple inheritance complexity. 2) When using trait, you need to pay attention to method conflicts, which can be resolved through the alternative and as keywords. 3) Overuse of trait should be avoided and its single responsibility should be maintained to optimize performance and improve code maintainability.

Dependency Injection Container (DIC) is a tool that manages and provides object dependencies for use in PHP projects. The main benefits of DIC include: 1. Decoupling, making components independent, and the code is easy to maintain and test; 2. Flexibility, easy to replace or modify dependencies; 3. Testability, convenient for injecting mock objects for unit testing.

SplFixedArray is a fixed-size array in PHP, suitable for scenarios where high performance and low memory usage are required. 1) It needs to specify the size when creating to avoid the overhead caused by dynamic adjustment. 2) Based on C language array, directly operates memory and fast access speed. 3) Suitable for large-scale data processing and memory-sensitive environments, but it needs to be used with caution because its size is fixed.

PHP handles file uploads through the $\_FILES variable. The methods to ensure security include: 1. Check upload errors, 2. Verify file type and size, 3. Prevent file overwriting, 4. Move files to a permanent storage location.

In JavaScript, you can use NullCoalescingOperator(??) and NullCoalescingAssignmentOperator(??=). 1.??Returns the first non-null or non-undefined operand. 2.??= Assign the variable to the value of the right operand, but only if the variable is null or undefined. These operators simplify code logic, improve readability and performance.


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

WebStorm Mac version
Useful JavaScript development tools

DVWA
Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

SublimeText3 Linux new version
SublimeText3 Linux latest version

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

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.