Pattern visualizer
Palindrome Partitioning II
Every valid partition ends its LAST piece somewhere — say it starts at index j and runs to the end of the current prefix. If that piece is a palindrome, then the cuts needed for the whole prefix are exactly one more than the cuts needed for everything before it: dp[i] = dp[j] + 1. Trying every j and keeping the smallest result gives dp[i] = min cuts for the first i characters. The worst case (cut before every letter) is always available as a fallback, so dp[i] never has to stay unset. Animated on: Given string s = "aab", partition it so every piece is a palindrome. Return the minimum number of cuts needed..
dp[i] = min over palindromic suffixes s[j..i-1] of dp[j] + 1
dp over "aab" — dp[i] = min cuts to partition the first i characters
dp[0] = -1: there's no prefix to cut yet, and this -1 is what makes "the whole prefix is itself a palindrome" cost 0 cuts once we add 1.
1FUNCTION minCut(s):2 n <- LENGTH(s)3 isPal <- precomputed palindrome table for all s[i..j]4 dp[0] <- -15 FOR i FROM 1 TO n:6 dp[i] <- i - 17 FOR j FROM 0 TO i - 1:8 IF isPal[j][i-1] = TRUE:9 dp[i] <- MIN(dp[i], dp[j] + 1)10 RETURN dp[n]
← / → step · space play · Home restart