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 < 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:
- Iterate through all index pairs (i, j), such that i < j, and check isPrefixAndSuffix(words[i], words[j]).
- 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:
- 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!

Hot AI Tools

Undress AI Tool
Undress images for free

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

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

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics











Upgrading the PHP version is actually not difficult, but the key lies in the operation steps and precautions. The following are the specific methods: 1. Confirm the current PHP version and running environment, use the command line or phpinfo.php file to view; 2. Select the suitable new version and install it. It is recommended to install it with 8.2 or 8.1. Linux users use package manager, and macOS users use Homebrew; 3. Migrate configuration files and extensions, update php.ini and install necessary extensions; 4. Test whether the website is running normally, check the error log to ensure that there is no compatibility problem. Follow these steps and you can successfully complete the upgrade in most situations.

To set up a PHP development environment, you need to select the appropriate tools and install the configuration correctly. ①The most basic PHP local environment requires three components: the web server (Apache or Nginx), the PHP itself and the database (such as MySQL/MariaDB); ② It is recommended that beginners use integration packages such as XAMPP or MAMP, which simplify the installation process. XAMPP is suitable for Windows and macOS. After installation, the project files are placed in the htdocs directory and accessed through localhost; ③MAMP is suitable for Mac users and supports convenient switching of PHP versions, but the free version has limited functions; ④ Advanced users can manually install them by Homebrew, in macOS/Linux systems

TosetupaPHPdevelopmentenvironmentonLinux,installPHPandrequiredextensions,setupawebserverlikeApacheorNginx,testwithaPHPfile,andoptionallyinstallMySQLandComposer.1.InstallPHPandextensionsviapackagemanager(e.g.,sudoaptinstallphpphp-mysqlphp-curlphp-mbst

To merge two PHP arrays and keep unique values, there are two main methods. 1. For index arrays or only deduplication, use array_merge and array_unique combinations: first merge array_merge($array1,$array2) and then use array_unique() to deduplicate them to finally get a new array containing all unique values; 2. For associative arrays and want to retain key-value pairs in the first array, use the operator: $result=$array1 $array2, which will ensure that the keys in the first array will not be overwritten by the second array. These two methods are applicable to different scenarios, depending on whether the key name is retained or only the focus is on

To determine the strength of the password, it is necessary to combine regular and logical processing. The basic requirements include: 1. The length is no less than 8 digits; 2. At least containing lowercase letters, uppercase letters, and numbers; 3. Special character restrictions can be added; in terms of advanced aspects, continuous duplication of characters and incremental/decreasing sequences need to be avoided, which requires PHP function detection; at the same time, blacklists should be introduced to filter common weak passwords such as password and 123456; finally it is recommended to combine the zxcvbn library to improve the evaluation accuracy.

TopreventCSRFattacksinPHP,implementanti-CSRFtokens.1)Generateandstoresecuretokensusingrandom_bytes()orbin2hex(random_bytes(32)),savethemin$_SESSION,andincludetheminformsashiddeninputs.2)ValidatetokensonsubmissionbystrictlycomparingthePOSTtokenwiththe

To safely handle PHP file uploads, you need to verify the source and type, control the file name and path, set server restrictions, and process media files twice. 1. Verify the upload source to prevent CSRF through token and detect the real MIME type through finfo_file using whitelist control; 2. Rename the file to a random string and determine the extension to store it in a non-Web directory according to the detection type; 3. PHP configuration limits the upload size and temporary directory Nginx/Apache prohibits access to the upload directory; 4. The GD library resaves the pictures to clear potential malicious data.

There are three common methods for PHP comment code: 1. Use // or # to block one line of code, and it is recommended to use //; 2. Use /.../ to wrap code blocks with multiple lines, which cannot be nested but can be crossed; 3. Combination skills comments such as using /if(){}/ to control logic blocks, or to improve efficiency with editor shortcut keys, you should pay attention to closing symbols and avoid nesting when using them.
