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

<p>A <strong>palindrome pair</strong> is a pair of integers <code>(i, j)</code> such that:</p>

<ul>
	<li><code>0 &lt;= i, j &lt; words.length</code>,</li>
	<li><code>i != j</code>, and</li>
	<li><code>words[i] + words[j]</code> (the concatenation of the two strings) is a <span data-keyword="palindrome-string">palindrome</span>.</li>
</ul>

<p>Return <em>an array of all the <strong>palindrome pairs</strong> of </em><code>words</code>.</p>

<p>You must write an algorithm with&nbsp;<code>O(sum of words[i].length)</code>&nbsp;runtime complexity.</p>

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

<pre>
<strong>Input:</strong> words = [&quot;abcd&quot;,&quot;dcba&quot;,&quot;lls&quot;,&quot;s&quot;,&quot;sssll&quot;]
<strong>Output:</strong> [[0,1],[1,0],[3,2],[2,4]]
<strong>Explanation:</strong> The palindromes are [&quot;abcddcba&quot;,&quot;dcbaabcd&quot;,&quot;slls&quot;,&quot;llssssll&quot;]
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;bat&quot;,&quot;tab&quot;,&quot;cat&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;battab&quot;,&quot;tabbat&quot;]
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;a&quot;,&quot;a&quot;]
</pre>

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>0 &lt;= words[i].length &lt;= 300</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        ios_base::sync_with_stdio(false);
		cin.tie(NULL);
        /*
            use uno_map for storing index

            1. handle empty
            2. handle reveresed
            3. handle if left is palindrome then search for reverse of right
            4. hanle if right is palindrome then search for reverse of left

        */

        int n = words.size();
        unordered_map<string_view,int> mp;
        int len[301] = {0}; // store ki kitte length ki kitni strings hai

        for(int i = 0; i < n; i++){
            // string temp = words[i];
            // reverse(temp.begin(), temp.end());
            mp[words[i]] = i;
            len[words[i].size()] = 1; // stores that we have this length string
        }

        // if empty
        vector<vector<int>> ans;

        auto it = mp.find("");
        
        if(it != mp.end()){
            int emptyIdx = it->second;
            for(int i = 0; i < n; i++){
                if(i != emptyIdx and isPalindrome(words[i], 0, words[i].size() - 1)){
                    ans.push_back({emptyIdx, i});
                    ans.push_back({i, emptyIdx});
                }
            }
        }


        // handle reflection case
        for(int i = 0; i < n; i++){
            string rev = words[i];
            reverse(rev.begin(), rev.end());

            auto it = mp.find(rev);
            if(it != mp.end() and it->second != i){
                ans.push_back({i, it->second});
            }
        }


        // handle other two cases
        for(int i = 0; i < n; i++){
            string &curr = words[i];
            int m = curr.size();
            for(int cut = 1; cut < m; cut++){
                // string left = curr.substr(0, cut);
                // string right = curr.substr(cut); // cut to last

                if(isPalindrome(curr, 0, cut - 1)){
                    string revRight = curr.substr(cut);;
                    reverse(revRight.begin(), revRight.end());
                    // right + left
                    auto it = mp.find(revRight);
                    if(it != mp.end()){
                        ans.push_back({it->second, i});
                    }
                }

                if(isPalindrome(curr, cut, m - 1)){
                    string revLeft = curr.substr(0, cut);
                    reverse(revLeft.begin(), revLeft.end());
                    auto it = mp.find(revLeft);
                    // left + right
                    if(it != mp.end()){
                        ans.push_back({i, it->second});
                    }
                }
            }
        }



        return ans;
    }

    bool isPalindrome(const string &str, int low, int high) {
        while(low <= high) {
            if(str[low] != str[high]) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
};


/*
==> bext approach: map se

case1: mathches with the reverse of the word
    case2: word1[0, i] == reverse(word2) anddddd word1[i+1, n1 - 1] ==> this is a palindrome
    case3: word1 == word2[n2-n1, n2-1](last n1 characters)[reverse it] and then match = word2[n2-1, n2-n1])
            andddddd word2[0, n2 - n1 - 1] ==> palindrome


    case1: complete match with reversed
    case2: prefix of word1 matched with reverse of word2 and remaining word1 is palindrome
    case3: word1 matched with reverse of suffix of word2 and string from 0 to n2-n1-1 is palindrome
            or reverse of word1 matches with suffix


// simnce strings are unique handle the case of "" separately
use unom for storing index

1. handle empty
2. handle reveresed
3. handle if left is palindrome then search for reverse of right
4. hanle if right is palindrome then search for reverse of left









brute force: combine each word with other and then check for palindrome


========> Main approcah:

build trie

then try to match the reverse of each word ==> only skip the current palindrome one ==> hold the index
    only checking the reverse will not work =======> because can be divided 


there can be two cases:
    1> tbc [exe] (cbt) ==> cbt will be the other part, becasue exe is palindrome
    2> tbcex [e] xecbt ==> because one character e is always palindrome


    see: https://leetcode.com/problems/palindrome-pairs/?envType=company&envId=google&favoriteSlug=google-six-months&status=TO_DO

    case1: mathches with the reverse of the word
    case2: word1[0, i] == reverse(word2) anddddd word1[i+1, n1 - 1] ==> this is a palindrome
    case3: word1 == word2[n2-n1, n2-1](last n1 characters)[reverse it] and then match = word2[n2-1, n2-n1])
            andddddd word2[0, n2 - n1 - 1] ==> palindrome


    case1: complete match with reversed
    case2: prefix of word1 matched with reverse of word2 and remaining word1 is palindrome
    case3: word1 matched with reverse of suffix of word2 and string from 0 to n2-n1-1 is palindrome
            or reverse of word1 matches with suffix
    

    in this way each time reverse of word is being matched ===> so we can store the revesed words in the trie/map

    word1 == reverse(word2)

    [str1] [word1_rem], rev(word2) ===> str1 == rev(word2) and word1_Rem is palindrome ==> ans = word1 + word2

    rev(word1), [str1] [word2_rem] ===> word2_rem == rev(word1) and str1 is palindrome => ans = word1 + word2 ==> but word1 is from trie so make sure to return the index


steps:
    1. build trie with reversed words
    2.1: try to match with reversed word
    2.2: match prefix with rev word from trie and remaiing word(suffix) is palindrome
    2.3: match suffix with rev from trie and remaining word (prefix) is palindrome




Memory limit error:




class Node {
public:
    Node *child[26] = {NULL};
    int idx;
    int data;

    Node(int d) {
        data = d;
        idx = -1; // initially
    }
};

class Trie {
public:
    Node *root;

    Trie() {
        root = new Node('\0'); // end of string
    }

    void insert(const string &str, const int &idx, const int &n) {
        Node *temp = root;
        for(int i = n - 1; i >= 0; i--) {
            int d = str[i] - 'a';
            if(temp->child[d]) {
                temp = temp->child[d];
            } else {
                Node *newNode = new Node(d);
                temp->child[d] = newNode;
                temp = newNode;
            }
        }
        temp->idx = idx; // terminal mark
    }

    int search(const string &str, const int &idx) {
        int n = str.size();
        Node *temp = root;
        for(int i = 0; i < n; i++) {
            int d = str[i] - 'a';
            if(temp->child[d]) {
                temp = temp->child[d];
            } else {
                return -1; // not found
            }
        }

        if(temp->idx == idx) {
            // same word is palindrome
            return -1; // not found
        }

        return temp->idx; // found
    }
};

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        Trie *t = new Trie();
        int n = words.size();

        // Insert reversed words into the Trie
        for(int i = 0; i < n; i++) {
            int m = words[i].size();
            t->insert(words[i], i, m); // reversed and inserted
        }

        vector<vector<int>> ans;

        for(int i = 0; i < n; i++) {
            string word = words[i];
            int m = word.size();

            if(m == 0) {
                // Handle the empty string case
                for(int j = 0; j < n; j++) {
                    if(j != i && isPalindrome(words[j], 0, words[j].size() - 1)) {
                        ans.push_back({i, j}); // empty + palindrome
                        ans.push_back({j, i}); // palindrome + empty
                    }
                }
                continue;
            }

            // Case 1: Full reverse match
            string rev = word;
            reverse(rev.begin(), rev.end());
            int idx = t->search(rev, i);
            if(idx != -1) {
                ans.push_back({i, idx}); // word1 -> i, word2-> idx
            }

            // Case 2: Prefix matches with reverse of some word, remaining is palindrome
            for(int j = 0; j < m; j++) {
                string prefix = getPrefixIfRemainingPalindrome(word, j, m); // this can return ""
                if(!prefix.empty()) {
                    idx = t->search(prefix, i);
                    if(idx != -1) {
                        ans.push_back({i, idx}); // word1 -> i, word2-> idx
                    }
                }
            }

            // Case 3: Suffix matches with reverse of some word, remaining is palindrome
            for(int j = 0; j < m; j++) {
                string suffix = getSuffixIfRemainingPalindrome(word, j, m); // // this can return ""
                if(!suffix.empty()) {
                    idx = t->search(suffix, i);
                    if(idx != -1) {
                        ans.push_back({idx, i}); // word1 -> idx, word2-> i
                    }
                }
            }
        }

        return ans;
    }

    string getPrefixIfRemainingPalindrome(const string &str, int i, int n) {
        int low = i + 1, high = n - 1;
        if(isPalindrome(str, low, high)) {
            int len = i + 1;
            return str.substr(0, len);
        }
        return "";
    }

    string getSuffixIfRemainingPalindrome(const string &str, int i, int n) {
        int low = 0, high = i;
        if(isPalindrome(str, low, high)) {
            int len = n - i - 1; // (n - (i+1))
            return str.substr(i + 1, len);
        }
        return "";
    }

    bool isPalindrome(const string &str, int low, int high) {
        while(low <= high) {
            if(str[low] != str[high]) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
};

*/
444578