1 题目描述
给出一个字符串s，分割s使得分割出的每一个子串都是回文串 计算将字符串s分割成回文分割结果的最小切割数 例如:给定字符串s=“aab”, 返回1，因为回文分割结果[“aa”,“b”]是切割一次生成的。
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. For example, given s =“aab”, Return1since the palindrome partitioning[“aa”,“b”]could be produced using 1 cut.
示例1
输入
“aab”
输出
1
2 解题思路
动态规划，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]代表源字符串第
i
i
i个字母到第
j
j
j个字母(包含
j
j
j)的子字符串的最小切割数。
3 代码实现
class Solution {
public:
int minCut(string s
) {
int n
= s
.size();
if(isPalindrome(s
, 0, n
- 1)) return 0;
vector
<vector
<int>> dp(n
, vector
<int>(n
, 0X7FFFFFFF));
for(int i
= 0; i
< n
; i
++)
dp
[i
][i
] = 0;
for(int rightSubLeft
= 1; rightSubLeft
< n
; rightSubLeft
++)
for(int left
= 0, right
= left
+ rightSubLeft
; right
< n
; left
++, right
++){
if(isPalindrome(s
, left
, right
)){
dp
[left
][right
] = 0;
continue;
}
for(int mid
= left
; mid
< right
; mid
++)
dp
[left
][right
] = min(dp
[left
][right
], dp
[left
][mid
] + dp
[mid
+ 1][right
] + 1);
}
return dp
[0][n
- 1];
}
bool isPalindrome(string
&s
, int left
, int right
){
while(left
< right
)
if(s
[left
] == s
[right
]){
left
++;
right
--;
}
else
return false;
return true;
}
};
4 运行结果
运行时间：24ms 占用内存：1368k
