LeetCode-132. Palindrome Partitioning II

LeetCode-132. Palindrome Partitioning II

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: 1Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

题解：

用函数判断效率很低：

class Solution {public: bool isPalindrome (string &s) { int n = s.length(); for (int i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) { return false; } } return true; } int minCut(string &s) { int n = s.length(); vector dp(n + 1, 0); dp[0] = -1; for (int i = 0; i < n; i++) { dp[i + 1] = i; } for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { string sub = s.substr(j, i - j); if (isPalindrome(sub) == true) { dp[i] = min(dp[j] + 1, dp[i]); } } } return dp[n]; }};

即时判断：

class Solution {public: int minCut(string s) { int n = s.length(); vector dp(n + 1, 0); dp[0] = -1; for (int i = 0; i < n; i++) { dp[i + 1] = i; } for (int i = 0; i < n; i++) { int j = 0; while (j <= i && j < n - 1 && s[i + j] == s[i - j]) { dp[i + j + 1] = min(dp[i + j + 1], dp[i - j] + 1); j++; } j = 0; while(j <= i - 1 && j < n - i && s[i + j] == s[i - j - 1]) { dp[i + j + 1] = min(dp[i + j + 1], dp[i - j - 1] + 1); j++; } } return dp[n]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。