Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/132.html
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 1:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
Input: s = "a" Output: 0
Example 3:
Input: s = "ab" Output: 1
Constraints:
1 <= s.length <= 2000sconsists of lowercase English letters only.
Algorithm
One-dimensional dp array, where dp[i] represents the minimum number of divisions in the range of substring [0, i].
Use a two-dimensional dp array p, where p[i][j] indicates whether the substring in the interval [i, j] is a palindrome, and the state transition equation is p[i][j] = (s[i] == s[j]) && p[i+1][j-1], where p[i][j] = true if [i, j] is a palindrome.
Code
-
class Solution { public int minCut(String s) { int n = s.length(); boolean[][] dp1 = new boolean[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { dp1[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp1[i + 1][j - 1]); } } int[] dp2 = new int[n]; for (int i = 0; i < n; i++) { if (!dp1[0][i]) { dp2[i] = i; for (int j = 1; j <= i; j++) { if (dp1[j][i]) { dp2[i] = Math.min(dp2[i], dp2[j - 1] + 1); } } } } return dp2[n - 1]; } } ////// public class Palindrome_Partitioning_II { public class Solution { public int minCut(String s) { if (s == null || s.length() == 0) { return -1; } // 'abcba', when reaching 'c', minCut=2 // when reaching 2nd 'b', minCut=1 // when reaching 2nd 'a', minCut=0 // so, if a substring is palindrome, cut is prev_segment+1 // set up a fast lookup for if palindrome from i to j boolean[][] isPal = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) { for (int j = i; j >= 0; j--) { if (i == j || (s.charAt(i) == s.charAt(j) && (i - j == 1 || isPal[j + 1][i - 1]))) { isPal[j][i] = true; // j is first, then i } } } // set up min count array, worst case, each char is a palindrome int[] minCut = new int[s.length()]; for (int i = 0; i < s.length(); i++) { minCut[i] = i; } // how to cound, eg: 'aabcba', 'aabcbaz' // @note: if a substring is palindrome, cut is prev_segment+1 for (int i = 0; i < s.length(); i++) { for (int j = 0; j < s.length(); j++) { if (isPal[i][j]) { if (i - 1 >= 0) { // @note: eg, 'aabcba' minCut[j] = Math.min(minCut[j], 1 + minCut[i - 1]); } else { // i.e., i==0. eg, 'abcba' minCut[j] = 0; } } } } int min = minCut[s.length() - 1]; return min; } } } -
class Solution { public: int minCut(string s) { int n = s.size(); vector<vector<bool>> dp1(n, vector<bool>(n)); for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) { dp1[i][j] = s[i] == s[j] && (j - i < 3 || dp1[i + 1][j - 1]); } } vector<int> dp2(n); for (int i = 0; i < n; ++i) { if (!dp1[0][i]) { dp2[i] = i; for (int j = 1; j <= i; ++j) { if (dp1[j][i]) { dp2[i] = min(dp2[i], dp2[j - 1] + 1); } } } } return dp2[n - 1]; } }; -
class Solution: def minCut(self, s: str) -> int: pal = [[False for j in range(0, len(s))] for i in range(0, len(s))] dp = [len(s) for _ in range(0, len(s) + 1)] for i in range(0, len(s)): for j in range(0, i + 1): # also ok if, (j + 1 >= i - 1) if (s[i] == s[j]) and ((j + 1 > i - 1) or (pal[i - 1][j + 1])): pal[i][j] = True dp[i + 1] = min(dp[i + 1], dp[j] + 1) if j != 0 else 0 # 'if j != 0' to ensure from start to i is a palindrome return dp[-1] ############ class Solution: # clear cache def minCut(self, s: str) -> int: @cache def dfs(i): if i >= n - 1: return 0 ans = inf for j in range(i, n): if g[i][j]: ans = min(ans, dfs(j + 1) + (j < n - 1)) return ans n = len(s) g = [[True] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i + 1, n): g[i][j] = s[i] == s[j] and g[i + 1][j - 1] ans = dfs(0) dfs.cache_clear() # nice, clear cache !!! return ans ############ class Solution: def minCut(self, s: str) -> int: n = len(s) is_pal = [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i, n): is_pal[i][j] = s[i] == s[j] and (j - i < 3 or is_pal[i + 1][j - 1]) min_cut = [i for i in range(n)] for i in range(n): for j in range(0, i + 1): if is_pal[j][i]: min_cut[i] = min(min_cut[i], min_cut[j - 1] + 1) if j > 0 else 0 return min_cut[-1] -
func minCut(s string) int { n := len(s) dp1 := make([][]bool, n) for i := 0; i < n; i++ { dp1[i] = make([]bool, n) } for i := n - 1; i >= 0; i-- { for j := i; j < n; j++ { dp1[i][j] = s[i] == s[j] && (j-i < 3 || dp1[i+1][j-1]) } } dp2 := make([]int, n) for i := 0; i < n; i++ { if !dp1[0][i] { dp2[i] = i for j := 1; j <= i; j++ { if dp1[j][i] { dp2[i] = min(dp2[i], dp2[j-1]+1) } } } } return dp2[n-1] } func min(x, y int) int { if x < y { return x } return y } -
using System; using System.Collections.Generic; public class Solution { public int MinCut(string s) { if (s.Length == 0) return 0; var paths = new List<int>[s.Length]; for (var i = 0; i < s.Length; ++i) { int j, k; for (j = i, k = i + 1; j >= 0 && k < s.Length; --j, ++k) { if (s[j] == s[k]) { if (paths[k] == null) { paths[k] = new List<int>(); } paths[k].Add(j - 1); } else { break; } } for (j = i, k = i; j >= 0 && k < s.Length; --j, ++k) { if (s[j] == s[k]) { if (paths[k] == null) { paths[k] = new List<int>(); } paths[k].Add(j - 1); } else { break; } } } var partCount = new int[s.Length]; for (var i = 0; i < s.Length; ++i) { partCount[i] = int.MaxValue; if (paths[i] != null) { foreach (var path in paths[i]) { if (path < 0) { partCount[i] = 0; break; } else { partCount[i] = Math.Min(partCount[i], partCount[path]); } } } ++partCount[i]; } return partCount[s.Length - 1] - 1; } } -
function minCut(s: string): number { const n = s.length; const g: boolean[][] = Array(n) .fill(0) .map(() => Array(n).fill(true)); for (let i = n - 1; ~i; --i) { for (let j = i + 1; j < n; ++j) { g[i][j] = s[i] === s[j] && g[i + 1][j - 1]; } } const f: number[] = Array(n) .fill(0) .map((_, i) => i); for (let i = 1; i < n; ++i) { for (let j = 0; j <= i; ++j) { if (g[j][i]) { f[i] = Math.min(f[i], j ? 1 + f[j - 1] : 0); } } } return f[n - 1]; }