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

目录

一、题目描述

二、解题思路

【C++】

【Java】

---

Leetcode-132.Palindrome Partitioning IIhttps://leetcode.com/problems/palindrome-partitioning-ii/description/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/

一、题目描述

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 <= 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<int> 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<vector<int>> isPalindrome(s.size(), vector<int>(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<int> 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];}
}