@algorithm.ts/manacher v4.0.3
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.
Install
npm
npm install --save @algorithm.ts/manacher
yarn
yarn add @algorithm.ts/manacher
Usage
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] }
Related
9 months ago
10 months ago
1 year ago
1 year ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
4 years ago
4 years ago
4 years ago
4 years ago
4 years ago