Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 132 with 20 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 132 # by problem number
lcpy gen -s palindrome_partitioning_ii # by problem name
s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Input: s = "a"
Output: 0
Input: s = "ab"
Output: 1
1 <= s.length <= 2000s consists of lowercase English letters only.class Solution:
# Time: O(n^2)
# Space: O(n^2)
def min_cut(self, s: str) -> int:
n = len(s)
is_pal = [[False] * n for _ in range(n)]
cut = [0] * n
for i in range(n):
best = n
for j in range(i + 1):
if s[j] == s[i] and (i - j < 2 or is_pal[j + 1][i - 1]):
is_pal[j][i] = True
best = 0 if j == 0 else min(best, cut[j - 1] + 1)
cut[i] = best
return cut[n - 1]
| Time | Space |
|---|---|
| O(n^2) | O(n^2) |