[leetcode] 132. Palindrome Partitioning II

[leetcode] 132. 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:

Input:

"aab"

Output:

1

Explanation:

The palindrome partitioning ["aa","b"] could be produced using 1 cut.

分析

题目的意思是：给定一个字符串，现在分成几个字串，使得每个字串都是回文子串，求最小的分隔数。

定义状态数组: dp[n], dp[j]表示从0到j(包含j)的子串所需要用到的最小的切割次数状态转移方程: 当子串str[i…j]是一个回文子串时, dp[j] = min(dp[i-1] + 1, dp[i])动态规划，设字符串的的坐标为0,1,…,i,i+1,…,j,j+1。如果i~j是回文子串，那么最小切分次数等于前i个字符串的切分数+1，或者当前的切分数目。即dp[j+1] = min(dp[j+1],dp[i]+1)

代码

class Solution {public: int minCut(string s) { if(s.empty()){ return 0; } int n=s.length(); vector> p(n,vector(n)); vector dp(n); for(int i=0;i

参考文献

​​[编程题]palindrome-partitioning-ii​​​​[LeetCode] Palindrome Partitioning II 拆分回文串之二​​

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