Palindrome Pairs - Efficient Solution with Trie Data Structure

{"title":"Palindrome Pairs - Efficient Solution with Trie Data Structure","description":"This code implements a solution to find all palindrome pairs within a given list of strings. It leverages a Trie data structure for efficient search and memory management, addressing common memory allocation errors.","keywords":"palindrome pairs, trie, data structure, algorithm, leetcode, efficient, memory management, bad_alloc, solution","content":"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(1500000); this.order = new Array(1500000); this.reverCnt = 0; this.orderCnt = 0; for (let i = 0; i < 1500000; i++) { this.rever[i] = { index: 0, childs: [] }; this.order[i] = { index: 0, childs: [] }; } } 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; }//执行出错：terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc内容：The code is throwing a std::bad_alloc error because it runs out of memory. The rever and order arrays are initialized with a size of 1500000, which may be too large and cause the program to run out of memory.

To fix this issue, you can try reducing the size of the arrays or optimizing the code to use less memory. Additionally, you can check if there are any memory leaks or other issues that may be causing the program to consume too much memory.