LeetCode 132 Palindrome Partitioning II - Implementation

Phase $1$: Build isPalin table. Iterate by length. $isPalin[i][i]$ = true. $isPalin[i][i+1]$ = ($s[i]$ == $s[i+1]$). For longer: check ends match and inner is palindrome.

Phase $2$: Compute $cuts[i]$ for each position. Check if whole prefix is palindrome ($0$ cuts). Otherwise try all valid last palindrome positions. Answer is $cuts[n-1]$. Time: $O(n^2)$, Space: $O(n^2)$ for isPalin table. Trace through a small example to verify your understanding before moving on.

Time complexity: $O(n^2)$.

Space complexity: $O(n^2)$.