Problem Description
You are given a 0-indexed string array words. Define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2, returning true if str1 is both a prefix and a suffix of str2, otherwise returning false. Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.
Key Insights
- The prefix of a string is a substring that starts from the beginning.
- The suffix of a string is a substring that ends at the end.
- For each pair of strings
(words[i], words[j]), we need to check if one is both a prefix and suffix of the other. - Efficiently checking for valid pairs is crucial due to the constraints.
Space and Time Complexity
Time Complexity: O(n * m) in the worst case, where n is the number of words and m is the average length of the words, given the nested checks. Space Complexity: O(1) if we do not consider the input storage.
Solution
To solve this problem, we can iterate through each pair of indices (i, j) in the words array. For each pair, we will check if words[i] is a prefix and suffix of words[j]. To perform the check, we compare the lengths of the strings and use substring operations. This approach is straightforward but may not be optimal for larger inputs.