回文串的问题非常经典，也非经常见，涉及到递归，循环。动态规划等方面，这里总结一下几种类型，供以后回想，有问题请大家指正
1、回文串的推断 leetcode上的题目
bool isPalindrome(const char* src){ if(src == NULL)return true; int end = strlen(src)-1,begin = 0; while(begin < end)//从两边向中间推断，当然也能够从中间向两边推断 { if(src[begin] != src[end])return false; begin ++; end --; } return true;} 2、最长回文子串 leetcode上的题目 用方法一会超时
方法一：动态规划
void LongestPalindromeDP(const char* src)//DP算法{ if(src == NULL)return; int length = strlen(src); bool dp[length][length]; int i,j,len,maxLen = 1,begin = 0,end = 0; for(i = 0;i < length;i++) { memset(dp[i],false,sizeof(bool)*length); } for(len = 2;len <= length;len++) { for(i = 0;i + len - 1 < length;i++) { j = i+len-1; if(src[i] == src[j] && (j - i <= 2 || dp[i+1][j-1]))//dp[i][j]表示从第i到第j个元素是否为回文串 { dp[i][j] = true; begin = i; end = j; maxLen = len; } } } for(i = begin;i <= end;i++)cout << src[i]; cout << endl;} 方法二：从中间向两边扩展
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 == NULL)return; int length = strlen(src); int i,maxLen = 1,begin = 0,end = 0; for(i = 0;i < length;i++) { int len = expandAroundCenter(src,i,i);//针对奇数 if(len > maxLen) { maxLen = len; begin = i - ((len-1) >> 1); end = i + ((len-1) >> 1); } len = expandAroundCenter(src,i,i+1);//针对偶数 if(len > maxLen) { maxLen = len; begin = i - ((len-1) >> 1); end = i + 1 + ((len-1) >> 1); } } for(i = begin;i <= end;i++)cout<< src[i]; cout << endl;} 3、给一个串，问最少加入几个字符使得该串变成回文串
比如：abcd须要加入3个，变成abcdcba
int changeToPalindrome(const char* src){ if(src == NULL)return 0; int length = strlen(src); int dp[length][length]; int i,j,len; for(i = 0;i < length;i++)memset(dp[i],0,sizeof(int)*length); for(len = 2;len <= length;len++) { for(i = 0;i + len - 1 < length;i++) { j = i + len - 1; if(src[i] == src[j])dp[i][j] = dp[i+1][j-1];//dp[i][j]表示从第i个到第j个须要加入的字符数 else dp[i][j] = 1 + min(dp[i+1][j],dp[i][j-1]);//在前面或者后面加入一个字符 } } return dp[0][length-1];} 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 ::max(); int MIN = numeric_limits ::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"< 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& hash){ set ::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 >& res,vector & v,set & 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 > partition(string s) { int length = s.size(); vector > res; vector v; set hash; if(length <= 0)return res; dfs(s,res,v,hash);//递归推断 return res;}