Let’s define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:
isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix 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 thati < j, andisPrefixAndSuffix(words[i], words[j])istrue.
Input: words =["a","aba","ababa","aa"]Output: 4Explanation: In this example, the counted index pairs are:i =0 and j =1 because isPrefixAndSuffix("a","aba")istrue.i =0 and j =2 because isPrefixAndSuffix("a","ababa")istrue.i =0 and j =3 because isPrefixAndSuffix("a","aa")istrue.i =1 and j =2 because isPrefixAndSuffix("aba","ababa")istrue.Therefore, the answer is4.
Example 2:
1
2
3
4
5
6
Input: words =["pa","papa","ma","mama"]Output: 2Explanation: In this example, the counted index pairs are:i =0 and j =1 because isPrefixAndSuffix("pa","papa")istrue.i =2 and j =3 because isPrefixAndSuffix("ma","mama")istrue.Therefore, the answer is2.
Example 3:
1
2
3
4
Input: words =["abab","ab"]Output: 0Explanation: In this example, the only valid index pair is i =0 and j =1, and isPrefixAndSuffix("abab","ab")isfalse.Therefore, the answer is0.
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 * 105.
We build a trie where each node represents a pair of characters: one from the prefix and one from the suffix (traversed in reverse). This allows us to efficiently count how many times a prefix-suffix pair has occurred so far. As we process each word, we traverse the trie, updating the count and accumulating the result whenever a matching prefix-suffix pair is found.
classSolution {
classTrieNode {
val children = mutableMapOf<Pair<Char, Char>, TrieNode>()
var count = 0 }
funcountPrefixSuffixPairs(words: Array<String>): Int {
val root = TrieNode()
var res = 0for (w in words) {
var node = root
val rev = w.reversed()
for (i in w.indices) {
val key = Pair(w[i], rev[i])
node = node.children.getOrPut(key) { TrieNode() }
res += node.count
}
node.count++ }
return res
}
}