Palindrome Pairs: Efficient Algorithm with TypeScript

interface Tree {
    index: number;
    childs: number[];
}

class Solution {
    private rever: Tree[];
    private order: Tree[];
    private reverCnt: number;
    private orderCnt: number;
    
    constructor() {
        this.rever = new Array<Tree>(1500000);
        this.order = new Array<Tree>(1500000);
        this.reverCnt = 0;
        this.orderCnt = 0;
    }
    
    public insert(word: string, index: number): void {
        let p1 = 0, p2 = 0, ch = 0;
        const n = word.length;
        
        for(let i = 0; i < n; ++i) {
            ch = word.charCodeAt(i) - 'a'.charCodeAt(0);
            
            if(!this.order[p1].childs[ch]) {
                this.order[p1].childs[ch] = ++this.orderCnt;
            }
            p1 = this.order[p1].childs[ch];

            ch = word.charCodeAt(n - 1 - i) - 'a'.charCodeAt(0);
            
            if(!this.rever[p2].childs[ch]) {
                this.rever[p2].childs[ch] = ++this.reverCnt;
            }
            p2 = this.rever[p2].childs[ch];
        }
        
        this.order[p1].index = this.rever[p2].index = index;
    }

    public isPalindrome(word: string, i: number, j: number): boolean {
        while(i < j) {
            if(word[i++] !== word[j--]) return false;
        }
        return true;
    }
    
    public searchRever(word: string, index: number, ret: number[][]): void {
        let p = 0;
        
        for(let i = 0; i < word.length; ++i) {
            const j = word.charCodeAt(i) - 'a'.charCodeAt(0);
            
            if(this.rever[p].index && this.isPalindrome(word, i, word.length - 1)) {
                ret.push([index - 1, this.rever[p].index - 1]);
            }
            
            if(!this.rever[p].childs[j]) {
                return;
            }
            
            p = this.rever[p].childs[j];
        }
        
        if(this.rever[p].index && this.rever[p].index !== index) {
            ret.push([index - 1, this.rever[p].index - 1]);
        }
    }
    public searchOrder(word: string, index: number, ret: number[][]): void {
        let p = 0;
        for(let i = word.length - 1; i >= 0; --i) {
            const j = word.charCodeAt(i) - 'a'.charCodeAt(0);
            
            if(this.order[p].index && this.isPalindrome(word, 0, i)) {
                ret.push([this.order[p].index - 1, index - 1]);
            }
            if(!this.order[p].childs[j]) {
                return;
            }
            p = this.order[p].childs[j];
        }
    }
    public palindromePairs(words: string[]): number[][] {
        for(let i = 0; i < words.length; ++i) {
            this.insert(words[i], i + 1);
        }
        const ret: number[][] = [];
        for(let i = 0; i < words.length; ++i) {
            this.searchRever(words[i], i + 1, ret);
            this.searchOrder(words[i], i + 1, ret);
        }
        this.rever.fill({ index: 0, childs: [] });
        this.order.fill({ index: 0, childs: [] });
        return ret;
    }
}

function palindromePairs(words: string[]): number[][] {
    const solution = new Solution();
    const result = solution.palindromePairs(words);
    return result;
}

This TypeScript code implements an efficient algorithm to find all palindrome pairs within a given array of strings. The algorithm leverages Trie data structures for optimal search performance. The code defines a Tree interface representing a node in the Trie and a Solution class that handles the insertion, search, and palindrome pair detection logic. The insert() method builds the Trie based on the input words, while the searchRever() and searchOrder() methods efficiently find palindrome pairs using the Trie. The palindromePairs() function orchestrates the process, returning an array of pairs representing the indices of the palindrome pairs in the original word array.