Palindrome Pairs - Find Palindrome Pairs in a String Array - 常规

{"title":"Palindrome Pairs - Find Palindrome Pairs in a String Array","description":"This code implements a solution for finding all palindrome pairs in a given array of strings. The algorithm utilizes a Trie-like data structure to efficiently store the words and their reverse counterparts, enabling fast palindrome checks.","keywords":"palindrome pairs, palindrome, string array, algorithm, trie, data structure, C++, TypeScript","content":"interface Tree {\n index: number;\n childs: number[];\n}\n\nclass Solution {\n private rever: Tree[];\n private order: Tree[];\n private reverCnt: number;\n private orderCnt: number;\n \n constructor() {\n this.rever = new Array(1500000);\n this.order = new Array(1500000);\n this.reverCnt = 0;\n this.orderCnt = 0;\n }\n \n public insert(word: string, index: number): void {\n let p1 = 0, p2 = 0, ch = 0;\n const n = word.length;\n \n for(let i = 0; i < n; ++i) {\n ch = word.charCodeAt(i) - 'a'.charCodeAt(0);\n \n if(!this.order[p1].childs[ch]) {\n this.order[p1].childs[ch] = ++this.orderCnt;\n }\n p1 = this.order[p1].childs[ch];\n\n ch = word.charCodeAt(n - 1 - i) - 'a'.charCodeAt(0);\n \n if(!this.rever[p2].childs[ch]) {\n this.rever[p2].childs[ch] = ++this.reverCnt;\n }\n p2 = this.rever[p2].childs[ch];\n }\n \n this.order[p1].index = this.rever[p2].index = index;\n }\n\n public isPalindrome(word: string, i: number, j: number): boolean {\n while(i < j) {\n if(word[i++] !== word[j--]) return false;\n }\n return true;\n }\n \n public searchRever(word: string, index: number, ret: number[][]): void {\n let p = 0;\n \n for(let i = 0; i < word.length; ++i) {\n const j = word.charCodeAt(i) - 'a'.charCodeAt(0);\n \n if(this.rever[p].index && this.isPalindrome(word, i, word.length - 1)) {\n ret.push([index - 1, this.rever[p].index - 1]);\n }\n \n if(!this.rever[p].childs[j]) {\n return;\n }\n \n p = this.rever[p].childs[j];\n }\n \n if(this.rever[p].index && this.rever[p].index !== index) {\n ret.push([index - 1, this.rever[p].index - 1]);\n }\n }\n \n public searchOrder(word: string, index: number, ret: number[][]): void {\n let p = 0;\n \n for(let i = word.length - 1; i >= 0; --i) {\n const j = word.charCodeAt(i) - 'a'.charCodeAt(0);\n \n if(this.order[p].index && this.isPalindrome(word, 0, i)) {\n ret.push([this.order[p].index - 1, index - 1]);\n }\n \n if(!this.order[p].childs[j]) {\n return;\n }\n \n p = this.order[p].childs[j];\n }\n }\n \n public palindromePairs(words: string[]): number[][] {\n for(let i = 0; i < words.length; ++i) {\n this.insert(words[i], i + 1);\n }\n \n const ret: number[][] = [];\n \n for(let i = 0; i < words.length; ++i) {\n this.searchRever(words[i], i + 1, ret);\n this.searchOrder(words[i], i + 1, ret);\n }\n \n this.rever.fill({ index: 0, childs: [] });\n this.order.fill({ index: 0, childs: [] });\n \n return ret;\n }\n}\n