回文串的问题很经典，也很常见，涉及到递归，循环，动态规划等方面，这里总结一下几种类型，供以后回顾，有问题请大家指正

1、回文串的判断   leetcode上的题目

bool isPalindrome(const char* src)
{
	if(src =http://www.mamicode.com/= NULL)return true;>
2、最长回文子串  leetcode上的题目 用方法一会超时
方法一：动态规划
void LongestPalindromeDP(const char* src)//DP算法
{
	if(src =http://www.mamicode.com/= NULL)return;>
方法二：从中间向两边扩展
int expandAroundCenter(const char* src,int left,int right)//从中间往两头判断最长回文串
{
	int length = strlen(src);
	while(left >= 0 && right < length && src[left] == src[right])
	{
		left --;
		right ++;
	}
	return right - left - 1;
}
void LongestPalindromeCenter(const char* src)
{
	if(src =http://www.mamicode.com/= NULL)return;>
3、给一个串，问最少添加几个字符使得该串变成回文串
例如：abcd需要添加3个，变成abcdcba
int changeToPalindrome(const char* src)
{
	if(src =http://www.mamicode.com/= NULL)return 0;>
4、回文数字，leetcode上的题目
bool isPalindrome(int x) {
	if(x < 0)return false;
	int base = 1;
	while(x / 10 >=base)base *= 10;//获取最高位的权值
	while(x > 0)
	{
		int left = x / base;//最高位
		int right = x % 10;//最低位
		if( left != right)return false;
		x -= base*left;
		x /= 10;//除去最高最低位
		base /= 100;
	}
	return true;
}
附，把一个数字reverse
int reverseNum(int num)
{
	int MAX = numeric_limits<int>::max();
	int MIN = numeric_limits<int>::min();
	int res = 0,flag = 1;
	if(num < 0)flag = -1;
	while(num != 0)
	{
		int low = num % 10;//商和余数的符合和被除数相同
		if(flag == 1 && (MAX / 10 < res || (MAX / 10 == res && low > MAX % 10)))//溢出测试不能用乘法，要用除法
		{
			cout << "over flow 1"<<endl;
			return -1;
		}
		else if(flag == -1 && (MIN / 10 > res || (MIN / 10 == res && low < MIN % 10)))
		{
			cout << "over flow 2" << endl;
			return -1;
		}
		res = (res * 10)+low;
		num /= 10;
	}
	return res;
}

5、回文串的最小分割数  leetcode上的题目
int minCut(string s) {
	int length = s.size();
	if(length <= 0)return 0;
	bool isParlindrome[length][length];
	int i,j;
	for(i = 0;i < length;i++)
	{
		memset(isParlindrome[i],false,sizeof(bool)*length;
	}
	int dp[length+1];
	for(i = length;i >= 0;i--)dp[i] = length - i - 1;
	for(i = length-1;i >= 0 ;i--)
	{
		for(j = i;j < length;j++)
		{
			if(s[i] == s[j] && (j - i <= 2 || isParlindrome[i+1][j-1]))
			{
				isParlindrome[i][j] = true;
				dp[i] = min(dp[i],1+dp[j+1]);
			}
		}
	}
	return dp[0];
}

6、所有的分割回文串   leetcode上的题目
bool isPalindrome(string s,set<string>& hash)
{
	set<string>::iterator iter = hash.find(s);
	if(iter != hash.end())return true;//如果该部分已经判断过，则直接返回
	int i = 0,j = s.size()-1;
	while(i < j)
	{
		if(s[i++] != s[j--])return false;
	}
	hash.insert(s);
	return true;
}
void dfs(string s,vector<vector<string> >& res,vector<string>& v,set<string>& hash)
{
	int length = s.size();
	if(length == 0)
	{
		res.push_back(v);
		return;
	}
	int i;
	for(i = 1;i <= length;i++)
	{
		string sub = s.substr(0,i);
		if(isPalindrome(sub,hash))//首先判断前半部分是不是回文串
		{
			v.push_back(sub);
			dfs(s.substr(i),res,v,hash);//递归调用后半部分
			v.pop_back();
		}
	}
}
vector<vector<string> > partition(string s) {
	int length = s.size();
	vector<vector<string> > res;
	vector<string> v;
	set<string> hash;
	if(length <= 0)return res;
	dfs(s,res,v,hash);//递归判断
	return res;
}