<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>

from collections import defaultdict

class TrieNode:
    def __init__(self, chars):
        self.children = defaultdict(lambda: None)
        self.chars = chars
        self.count = 0

class Solution:
    # the hard part is figuring out a good trie construction
    # rest is aight

    # ab
    # abxxab

    # aa
    # aaa

    # from the left we want to see  a -> b -> a -> b -> a
    # from the right we want to see a -> b -> a -> b -> a

    # (l, r) we want to see (a, a) -> (b, b) -> ()

    def add_word_to_trie(self, root, word):
        curr = root
        for i in range(len(word)):
            tup = (word[i], word[len(word) - i - 1])
            if tup not in curr.children:
                curr.children[tup] = TrieNode(tup)

            if i == len(word) - 1:
                curr.children[tup].count += 1

            curr = curr.children[tup]

    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        result = 0
        root = TrieNode(("", ""))
        for word in words:
            # self.add_word_to_trie(root, word)
            curr = root
            L = len(word)
            for i in range(len(word)):
                tup = (word[i], word[len(word) - i - 1])
                if tup not in curr.children:
                    curr.children[tup] = TrieNode(tup)

                # print(f"'{word[:i+1]}', {curr.children[tup].count}")
                result += curr.children[tup].count
                if i == L - 1:
                    curr.children[tup].count += 1

                curr = curr.children[tup]

        return result

    # def countPrefixSuffixPairs(self, words: List[str]) -> int:
    #     def add_word_to_trie(trie_root, word):
    #         L = len(word)
    #         curr = trie_root
    #         rng = range(L)
    #         for i in rng:
    #             ch = word[i]
    #             if ch not in curr.children:
    #                 curr.children[ch] = TrieNode(ch)
    #             curr = curr.children[ch]
# 
    #         curr.count += 1
# 
    #     forward_trie = TrieNode("")
    #     reverse_trie = TrieNode("")
# 
    #     result = 0
# 
    #     for word in words:
    #         add_word_to_trie(forward_trie, word)
    #         add_word_to_trie(reverse_trie, word[::-1])
# 
    #         # print("at word", word)
    #         forward_curr = forward_trie
    #         reverse_curr = reverse_trie
    #         l = 0
    #         r = len(word) - 1
    #         while l <= len(word) - 1 and 0 <= r:
    #             # print(f"{word[:l+1]} <> {word[r:]}")
    #             forward_curr = forward_curr.children[word[l]]
    #             reverse_curr = reverse_curr.children[word[r]]
# 
    #             if not forward_curr or not reverse_curr:
    #                 # print("done!")
    #                 break
# 
    #             if forward_curr.count > 0 and reverse_curr.count > 0 and word[:l+1] == word[r:]:
    #                 if l == len(word) - 1 and forward_curr.count > 1:
    #                     # print(f"(a) FOUND! {forward_curr.count - 1} other occurences of {word[:l+1]}")
    #                     result += forward_curr.count - 1
    #                 elif l < len(word) - 1 or forward_curr.count > 1:
    #                     # print(f"(b) FOUND! {forward_curr.count} other occurences of {word[:l+1]}")
    #                     result += forward_curr.count
# 
    #             l += 1
    #             r -= 1
# 
    #     return result


2168