<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:
    
        res = 0

        trie = {}
        for w in words:
            cur = trie
            len_w = len(w)
            for idx in range(len_w):
                char1 = w[idx]
                char2 = w[len_w - idx - 1]
                if (char1, char2) not in cur:
                    cur[(char1, char2)] = {}
                cur = cur[(char1, char2)] 
                if "counter" in cur:
                    res += cur["counter"]
            if "counter" in cur:
                cur["counter"] += 1
            else:
                cur["counter"] = 1
            
        return res
                
        # res = 0

        # def get_prefix(words):
        #     res = {}
        #     for idx, w in enumerate(words):
        #         cur = res
        #         for char in w:
        #             if char not in cur:
        #                 cur[char] = {}
        #             cur = cur[char]
        #         if "val" in cur:
        #             cur["val"].append(idx)
        #         else:
        #             cur["val"] = [idx]
        #     return res
            
        # def get_suffix(words):
        #     res = {}
        #     for idx, w in enumerate(words):
        #         cur = res
        #         for char in reversed(w):
        #             if char not in cur:
        #                 cur[char] = {}
        #             cur = cur[char]
        #         if "val" in cur:
        #             cur["val"].append(idx)
        #         else:
        #             cur["val"] = [idx]
        #     return res
        
        # prefix = get_prefix(words)
        # suffix = get_suffix(words)

        # # def search(text, trie, self_idx):
        # #     res = set()
        # #     cur = trie
        # #     for char in text:
        # #         if char not in cur:
        # #             return res
        # #         cur = cur[char]
        # #     q = deque([cur]) 
        # #     while q:
        # #         cur = q.popleft()
        # #         if "val" in cur:
        # #             for val in cur["val"]:
        # #                 if val > self_idx:
        # #                     res.add((self_idx, val))
        # #         for k, v in cur.items():
        # #             if k != "val":
        # #                 q.append(v) 
        # #     return res
        # def search(text, prefix, suffix, self_idx):
        #     p_res = set()
        #     s_res = set()
        #     cur = prefix
        #     for char in text:
        #         cur = cur[char]
        #         if "val" in cur:
        #             for idx in cur["val"]:
        #                 if idx < self_idx:
        #                     p_res.add((idx, self_idx))

        #     cur = suffix
        #     for char in reversed(text):
        #         cur = cur[char]
        #         if "val" in cur:
        #             for idx in cur["val"]:
        #                 if idx < self_idx:
        #                     s_res.add((idx, self_idx))
            
        #     return len(p_res & s_res)

        # # for idx, w in enumerate(words):
        # #     prefixes = search(w, prefix, idx)
        # #     suffixes = search(reversed(w), suffix, idx)
        # #     res += len(prefixes & suffixes) 
        # for idx, w in enumerate(words):
        #     if idx != 0:
        #         res += search(w, prefix, suffix, idx)
            
        # return res
818