<p>You are given a <strong>0-indexed</strong> string array <code>words</code>.</p>

<p>Let&#39;s define a <strong>boolean</strong> function <code>isPrefixAndSuffix</code> that takes two strings, <code>str1</code> and <code>str2</code>:</p>

<ul>
	<li><code>isPrefixAndSuffix(str1, str2)</code> returns <code>true</code> if <code>str1</code> is <strong>both</strong> a <span data-keyword="string-prefix">prefix</span> and a <span data-keyword="string-suffix">suffix</span> of <code>str2</code>, and <code>false</code> otherwise.</li>
</ul>

<p>For example, <code>isPrefixAndSuffix(&quot;aba&quot;, &quot;ababa&quot;)</code> is <code>true</code> because <code>&quot;aba&quot;</code> is a prefix of <code>&quot;ababa&quot;</code> and also a suffix, but <code>isPrefixAndSuffix(&quot;abc&quot;, &quot;abcd&quot;)</code> is <code>false</code>.</p>

<p>Return <em>an integer denoting the <strong>number</strong> of index pairs </em><code>(i<em>, </em>j)</code><em> such that </em><code>i &lt; j</code><em>, and </em><code>isPrefixAndSuffix(words[i], words[j])</code><em> is </em><code>true</code><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;aba&quot;,&quot;ababa&quot;,&quot;aa&quot;]
<strong>Output:</strong> 4
<strong>Explanation:</strong> In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix(&quot;a&quot;, &quot;aba&quot;) is true.
i = 0 and j = 2 because isPrefixAndSuffix(&quot;a&quot;, &quot;ababa&quot;) is true.
i = 0 and j = 3 because isPrefixAndSuffix(&quot;a&quot;, &quot;aa&quot;) is true.
i = 1 and j = 2 because isPrefixAndSuffix(&quot;aba&quot;, &quot;ababa&quot;) is true.
Therefore, the answer is 4.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;pa&quot;,&quot;papa&quot;,&quot;ma&quot;,&quot;mama&quot;]
<strong>Output:</strong> 2
<strong>Explanation:</strong> In this example, the counted index pairs are:
i = 0 and j = 1 because isPrefixAndSuffix(&quot;pa&quot;, &quot;papa&quot;) is true.
i = 2 and j = 3 because isPrefixAndSuffix(&quot;ma&quot;, &quot;mama&quot;) is true.
Therefore, the answer is 2.  </pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;abab&quot;,&quot;ab&quot;]
<strong>Output:</strong> 0
<strong>Explanation: </strong>In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix(&quot;abab&quot;, &quot;ab&quot;) is false.
Therefore, the answer is 0.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= words[i].length &lt;= 10<sup>5</sup></code></li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
	<li>The sum of the lengths of all <code>words[i]</code> does not exceed <code>5 * 10<sup>5</sup></code>.</li>
</ul>

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        ans = 0

        seen = defaultdict(int)
        seen[words[0]] = 1
        lens = {len(words[0])}

        for i in range(1, len(words)):
            word = words[i]
            size = len(word)
            for j in lens:
                if j > size:
                    continue
                if j == size:
                    ans += seen[word] # 当且仅当自身时满足 e.g.only "pa" is both prefix and suffix of "pa"
                else:
                    curr = word[:j]
                    if curr == word[size - j:]:
                        ans += seen[curr]
            lens.add(size)
            seen[word] += 1
        return ans

# class Trie:
#     def __init__(self):
#         self.children = {}

#     def insert(self, word, i) -> None:
#         prefix = {}
#         cur = self.children
#         for c in word:
#             if c not in cur:
#                 cur[c] = {}
#             cur = cur[c]
#             if "*" in cur:
#                 prefix[cur["@"]] = cur["%"]
#         cur["*"] = ""  # 标志该节点为叶子节点
#         cur["@"] = i # 上一个该节点的坐标
#         cur["%"] = cur.get("%",0)+1 # 该节点出现的数量
#         return prefix

# class Solution:
#     def countPrefixSuffixPairs(self, words: List[str]) -> int:
#         ans = 0
#         pre_trie = Trie()
#         suf_trie = Trie()
#         for i, word in enumerate(words):
#             prefix = pre_trie.insert(word, i)
#             suffix = suf_trie.insert(word[::-1], i)
#             for i in prefix:
#                 if i in suffix:
#                     ans += prefix[i]
#         return ans
368