Count Prefix and Suffix Pairs II
You are given a 0-indexed string array words.
Define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:
isPrefixAndSuffix(str1, str2)returnstrueifstr1is both a prefix and a suffix ofstr2, andfalseotherwise.
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
4The counted pairs are (0, 1), (0, 2), (0, 3), and (1, 2), so the answer is 4.
Example 2
Input
words = ["pa","papa","ma","mama"]Output
2The counted pairs are (0, 1) and (2, 3), so the answer is 2.
Constraints
- 1 <= words.length <= 10^5
- 1 <= words[i].length <= 10^5
- words[i] consists only of lowercase English letters.
- The sum of the lengths of all words[i] does not exceed 5 * 10^5.