本文主要是介绍[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.
For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.
思路
此题可以用动态规划求解。isPal[j][i]表示字符串s的子串s[j…i]是否为回文串,cut[i]表示子串s[0…i]所需要的最小分割数
代码
/**------------------------------------* 日期:2015-03-02* 作者:SJF0115* 题目: 132.Palindrome Partitioning II* 网址:https://oj.leetcode.com/problems/palindrome-partitioning-ii/* 结果:AC* 来源:LeetCode* 博客:---------------------------------------**/#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;class Solution {public:int minCut(string s) {int size = s.size();if(size == 0){return 0;}//if// isPal[i][j]表示字符串s的子串s[i,j]是否为回文串bool isPal[size][size];memset(isPal,0,sizeof(isPal));// cut[j]表示子串s[0,j]所需要的最小分割数int cut[size];// cut[0,i]for(int i = 0;i < size;++i){// [0,i]最多分割i次cut[i] = i;// 判断s[j,i]是否是回文串for(int j = 0;j <= i;++j){// s[j,i]是回文串if(s[j] == s[i] && (i - j <= 1 || isPal[j+1][i-1])){isPal[j][i] = true;// s[0,i]是回文串if(j == 0){cut[i] = 0;}//ifelse{cut[i] = min(cut[i],cut[j-1]+1);}//else}//if}//for}//forreturn cut[size-1];}};int main(){Solution s;string str("cabababcbc");cout<<s.minCut(str)<<endl;return 0;}
运行时间
这篇关于[LeetCode]132.Palindrome Partitioning II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!