Problem Description
You are given a 0-indexed string array words. You need to return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true, where isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2.
Key Insights
- The function checks if one string is both a prefix and suffix of another.
- For each pair of indices (i, j), we must check the prefix and suffix condition.
- The problem has manageable constraints, allowing a straightforward double loop solution.
Space and Time Complexity
Time Complexity: O(n^2 * m) where n is the number of words and m is the average length of the words (to check prefix and suffix conditions).
Space Complexity: O(1) since no additional data structures are used that grow with input size.
Solution
We can solve the problem using a nested loop to iterate through each pair of indices (i, j) where i < j. For each pair, we will check if the first string is both a prefix and a suffix of the second string. If the condition is met, we will increment our count. The algorithm primarily uses string operations to check the prefix and suffix.