132. Palindrome Partitioning II
給定一個字符串 s，將 s 分割，使得分割的每個子字符串都是回文。
返回將 s 分割成回文所需的最少切割次數。
範例：
輸入：s = "aab" 輸出：1 解釋：可以通過一次切割得到回文分割 ["aa","b"]。
Python
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
# Initialize a 2D array to store palindrome information
is_palindrome = [[False] * n for _ in range(n)]
# Every single character is a palindrome
for i in range(n):
is_palindrome[i][i] = True
# Check for palindrome substrings of length 2 and more
for length in range(2, n + 1):
for start in range(n - length + 1):
end = start + length - 1
if s[start] == s[end]:
if length == 2 or is_palindrome[start + 1][end - 1]:
is_palindrome[start][end] = True
# Initialize the cuts array where cuts[i] represents the minimum cuts
for substring s[0:i+1]
cuts = [float('inf')] * n
for i in range(n):
if is_palindrome[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_palindrome[j + 1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[-1]
47.95MB, 651ms
C++
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int minCut(string s) {
int n = s.length();
vector<vector<bool>> is_palindrome(n, vector<bool>(n, false));
// Every single character is a palindrome
for (int i = 0; i < n; ++i) {
is_palindrome[i][i] = true;
}
// Check for palindrome substrings of length 2 and more
for (int length = 2; length <= n; ++length) {
for (int start = 0; start <= n - length; ++start) {
int end = start + length - 1;
if (s[start] == s[end]) {
if (length == 2 || is_palindrome[start + 1][end - 1]) {
is_palindrome[start][end] = true;
}
}
}
}
// Initialize the cuts array where cuts[i] represents the minimum cuts for
substring s[0:i+1]
vector<int> cuts(n, INT_MAX);
for (int i = 0; i < n; ++i) {
if (is_palindrome[0][i]) {
cuts[i] = 0;
} else {
for (int j = 0; j < i; ++j) {
if (is_palindrome[j + 1][i]) {
cuts[i] = min(cuts[i], cuts[j] + 1);
}
}
}
}
return cuts[n - 1];
}
};
10.73MB, 65ms
Javascript
/**
* @param {string} s
* @return {number}
*/
var minCut = function(s) {
const n = s.length;
const isPalindrome = Array.from({ length: n }, () => Array(n).fill(false));
// Every single character is a palindrome
for (let i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
// Check for palindrome substrings of length 2 and more
for (let length = 2; length <= n; length++) {
for (let start = 0; start <= n - length; start++) {
const end = start + length - 1;
if (s[start] === s[end]) {
if (length === 2 || isPalindrome[start + 1][end - 1]) {
isPalindrome[start][end] = true;
}
}
}
}
// Initialize the cuts array where cuts[i] represents the minimum cuts for substring s[0:i+1]
const cuts = Array(n).fill(Infinity);
for (let i = 0; i < n; i++) {
if (isPalindrome[0][i]) {
cuts[i] = 0;
} else {
for (let j = 0; j < i; j++) {
if (isPalindrome[j + 1][i]) {
cuts[i] = Math.min(cuts[i], cuts[j] + 1);
}
}
}
}
return cuts[n - 1];
};
89.48MB, 252ms
