题目：
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.
题目分析：
给定一个字符串，将这个字符串切分；
得到的每个子字符串都是回文（从左向右 和 从右向左读到的字符串相同）。
返回所需的最低的切分次数；
例如：s = 【“aab”】
回文的分区 （“aa”，“b”）可以 使用 1次 来切分；
代码实现：
1、方法一 ：使用递归；(此方法的时间复杂度 过大)
#pragma once #include<string> //判断一个字符串是不是回文 bool Ispalindrom(string s) { char *str = (char *)s.c_str(); int len =s.size(); int left = 0 ; int right =len-1; while(left < right ) { if(str[left] ==str[right]) { left++; right--; } else return false; } return true; } //判断一个能不能被 cut切割成是回文 bool IsCutpalindrom(string s,int cut) { //要是 cut == 0；只需要判断当前的字符串是不是 回文就好了 if(cut == 0) { return Ispalindrom(s); } int len = s.size(); //要是当前要切的 cut还要大于 字符串的长度 //那么 这个字符串肯定 不能够被cut切分 if(cut > len) return false; if(len == 0) return false; //开始 for(int i =0 ;i < len;++i) { //得到左边的字符串 string left = s.substr(0,i+1); //得到右边的字符串 string right; if(i != len-1) { right = s.substr(i+1,len-i-1); } if(IsCutpalindrom(left,0)&&IsCutpalindrom(right,cut-1)) { return true; } } return false; } int minCut(string s) { int ret = 0 ; int length = s.size(); //要是当前 字符串 长度是 0 或者是 1，那么就不需要切分的 if(length == 0||length == 1) return 0; for(int i = 0;i < length;++i ) { if(IsCutpalindrom(s,i)) return i; } } 2、方法二；
主要思想：
mincut [i] = MIN(mincut[i],min[j+1]+1);
mincut [i]表示的是从 i位置到字符串的结尾 所需 的最小的切分次数；
Ispal[i][j] 保存的是 i - j位置的字符串是不是回文；
如果 i - j 位置内的字符串是 回文的话，那么 i位置的最小的切分数是 j+i的最小的切分数+1；
#include<vector> class Solution { public: int minCut(string s) { int length = s.size(); if(length == 0||length == 1) return 0; //保存的是 当前的 位置到 结束字符串的 最小的切分 vector<int> mincut; mincut.resize(length); vector<vector<bool>> Ispal; Ispal.resize(length); for(int i = 0 ;i < length;++i) { mincut[i] = length-1-i; Ispal[i].resize(length,false); } for(int i= length - 1;i >=0 ;--i) { for(int j = i ;j < length;++j) { //要是 i位置 与j位置的 字符相等 ，并且只有一个字符 ， 并且前面的也是回文的 if(s[i] == s[j]&&((j - i < 2)||(Ispal[i+1][j-1] == true))) { Ispal[i][j] = true; if( j == length -1) mincut[i] = 0; else { mincut[i] = (mincut[i] < mincut[j+1]+1)?mincut[i]:mincut[j+1]+1; } } } } return mincut[0]; } };
