Leetcode-132.Palindrome Partitioning II [C++][Java]

[Leetcode-132.Palindrome Partitioning IIhttps://leetcode.com/problems/palindrome-partitioning- ii/description/]( ii/description/ “Leetcode-132.Palindrome Partitioning II”)[132 分割回文串 II - 力扣（LeetCode）132 分割回文串 II - 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的 最少分割次数 。 示例 1：输入：s = “aab"输出：1解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。示例 2：输入：s = “a"输出：0示例 3：输入：s = “ab"输出：1 提示： * 1 <= s.length <= 2000 * s 仅由小写英文字母组成https://leetcode.cn/problems/palindrome-partitioning- ii/description/]( ii/description/ “132. 分割回文串 II - 力扣（LeetCode）”)

一、题目描述

Given a string s, partition s such that every substring of the partition is a palindrome. Return theminimum 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 <= 2000
• s consists of lowercase English letters only.

二、解题思路

方法一

• 时间复杂度：O(n⋅2^n)
• 空间复杂度：O(n)

【C++】

class Solution { private: bool isPalindrome(const string& s, int l, int r) { while (l <= r) if (s[l++] != s[r–]) return false; return true; } public: int minCut(string s) { vector f(s.size(), INT_MAX); for (int i = 0; i < s.size(); ++i) { if (isPalindrome(s, 0, i)) {f[i] = 0;} else { for (int j = 0; j < i; ++j) { if (isPalindrome(s, j + 1, i)) { f[i] = min(f[i], f[j] + 1); } } } } return f[s.size() - 1]; } };

【Java】

class Solution { private boolean isPalindrome(String s, int l, int r) { while (l <= r) if (s.charAt(l++) != s.charAt(r–)) return false; return true; } public int minCut(String s) { int[] f = new int[s.length()]; Arrays.fill(f, Integer.MAX_VALUE); for (int i = 0; i < s.length(); ++i) { if (isPalindrome(s, 0, i)) {f[i] = 0;} else { for (int j = 0; j < i; ++j) { if (isPalindrome(s, j + 1, i)) { f[i] = Math.min(f[i], f[j] + 1); } } } } return f[s.length() - 1]; } }

方法二

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)

【C++】

class Solution { public: int minCut(string s) { vector> isPalindrome(s.size(), vector(s.size(), true)); for (int i = s.size() - 1; i >= 0; –i) { for (int j = i + 1; j < s.size(); ++j) { isPalindrome[i][j] = (s[i] == s[j]) && isPalindrome[i + 1][j - 1]; } } vector f(s.size(), INT_MAX); for (int i = 0; i < s.size(); ++i) { if (isPalindrome[0][i]) {f[i] = 0;} else { for (int j = 0; j < i; ++j) { if (isPalindrome[j + 1][i]) { f[i] = min(f[i], f[j] + 1); } } } } return f[s.size() - 1]; } };

【Java】

class Solution {

public int minCut(String s) {

int[] f = new int[s.length()];

boolean[][] isPalindrome = new boolean[s.length()][s.length()];

for (int l = s.length() - 1; l >= 0; –l) {

for (int r = l; r < s.length(); ++r) {

isPalindrome[l][r] = (l == r)

? true

(s.charAt(l) == s.charAt(r)) && (l + 1 == r || isPalindrome[l + 1][r - 1]); } } for (int i = 0; i < s.length(); ++i) { f[i] = Integer.MAX_VALUE; if (isPalindrome[0][i]) {f[i] = 0;} else { for (int j = 0; j < i; ++j) { if (isPalindrome[j + 1][i]) { f[i] = Math.min(f[i], f[j] + 1); } } } } return f[s.length() - 1]; } }