A typescript implementation of the manacher algorithm.
Manacher is a linear time algorithm for listing all the palindromes that appear at the start of a given string.
If you are curious about this algorithm, you can visit here for more details.
-
npm
npm install --save @algorithm.ts/manacher
-
yarn
yarn add @algorithm.ts/manacher
-
A solution of https://leetcode.com/problems/palindrome-partitioning-ii/
import manacher from '@algorithm.ts/manacher' export function minCut(text: string): number { const N: number = text.length const radius: number[] = manacher(text) const dp: number[] = [0] for (let i = 1; i < N; ++i) { let answer: number = i < radius[i] * 2 ? 0 : dp[i - 1] + 1 if (answer > 0) { for (let k = 1; k < i; ++k) { if (i - k < radius[i + k] * 2) { answer = Math.min(answer, dp[k - 1] + 1) } } } dp[i] = answer } return dp[N - 1] }