Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:


Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def minCut(self, s: str) -> int:
        

Solutions:
class Solution:

	def minCut(self, s):
		if s == s[::-1]:
			return 0
		if any((s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1] for i in range(1, len(s)))):
			return 1
		cut = [x for x in range(-1, len(s))]
		for i in range(len(s)):
			(r1, r2) = (0, 0)
			while r1 <= i < len(s) - r1 and s[i - r1] == s[i + r1]:
				(cut[i + r1 + 1], r1) = (min(cut[i + r1 + 1], cut[i - r1] + 1), r1 + 1)
			while r2 <= i < len(s) - r2 - 1 and s[i - r2] == s[i + r2 + 1]:
				(cut[i + r2 + 2], r2) = (min(cut[i + r2 + 2], cut[i - r2] + 1), r2 + 1)
		return cut[-1]


class Solution:

	def minCut(self, s):
		if s == s[::-1]:
			return 0
		for i in range(1, len(s)):
			if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
				return 1
		cut = [x for x in range(-1, len(s))]
		for i in range(len(s)):
			j = 0
			while i - j >= 0 and i + j < len(s) and (s[i - j] == s[i + j]):
				if cut[i + j + 1] > cut[i - j] + 1:
					cut[i + j + 1] = cut[i - j] + 1
				j += 1
			j = 0
			while i - j >= 0 and i + j + 1 < len(s) and (s[i - j] == s[i + j + 1]):
				if cut[i + j + 2] > cut[i - j] + 1:
					cut[i + j + 2] = cut[i - j] + 1
				j += 1
		return cut[-1]


class Solution:

	def minCut(self, s):
		if not s:
			return 0
		if s == s[::-1]:
			return 0
		length = len(s)
		for i in range(1, length):
			if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
				return 1
		cut = [i for i in range(-1, length)]
		for i in range(length):
			(r1, r2) = (0, 0)
			while i - r1 >= 0 and i + r1 < len(s) and (s[i - r1] == s[i + r1]):
				cut[i + r1 + 1] = min(cut[i + r1 + 1], cut[i - r1] + 1)
				r1 += 1
			while i - r2 >= 0 and i + r2 + 1 < len(s) and (s[i - r2] == s[i + r2 + 1]):
				cut[i + r2 + 2] = min(cut[i + r2 + 2], cut[i - r2] + 1)
				r2 += 1
		return cut[-1]


class Solution:

	def minCut(self, s):
		if s == s[::-1]:
			return 0
		for i in range(1, len(s)):
			if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
				return 1
		n = len(s)
		is_pal = [[0] * n for _ in range(n)]
		dp = [n - 1] * n
		for i in range(n - 1, -1, -1):
			dp[i] = n - i - 1
			for j in range(i, n):
				if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]):
					is_pal[i][j] = 1
					if j == n - 1:
						dp[i] = 0
					elif dp[j + 1] + 1 < dp[i]:
						dp[i] = dp[j + 1] + 1
		return dp[0]