题目：https://leetcode-cn.com/problems/longest-palindromic-substring/
题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
解法
1. 中心扩展法
顾名思义，该方法的核心思路是，逐一检查字符串中可以构成中心的中间节点（具有如aba或者aa结构的即可视为一个中心节点）。
找到中心节点后，下一步就是确定回文字符串的left和right边界，对于aba结构来说，显然left和right边界即为a对应数组中的位置，而对于aa结构而言，先可以确定一个左边界，由于暂时无法确定后面是否存在多个a（如babaaaab，回文部分是baaaab，有四个a组成），故右边界仍需往下扫描，直到扫描到不是a的部分位置。
找到左右边界后，开始左右同时向两边扩展，若两边界上的元素一致，则继续往下探索，否则停止判断，记录该回文串的长度及下标。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Solution { public: string longestPalindrome(string s) { int left; int right; int leftSure=0; int rightSure=0; if(s.length()<2){ //如果字符串长度小于2，则直接返回，leetcode有一个测试用例是空字符串 return s; } for(int i=0;i<s.length()-1;i++){ //对字符串内容进行逐个扫描 if(i==s.length()-2){ //如果当前节点为字符串的倒数第二个字符，则只检测s[i]与s[i+1]，防止后续s[i+2]越界 if(s[i]==s[i+1]){ left = i; right = i+1; if((right-left)>(rightSure-leftSure)){ rightSure = right; leftSure = left; } } } else if(s[i]==s[i+1]||s[i]==s[i+2]){ //检测两种模式类型 if(s[i]==s[i+1]){ left = i; right = s.length()-1; for(int j=i+2 ;j<s.length();j++){ if(s[j]!=s[left]){ right = j-1; break; } } }else{ left = right = i+1; } //get finish left and right while(left>=1&&right<s.length()-1){ //开始向两边扩展 if(s[left-1]==s[right+1]){ left--; right++; }else{ break; } } if((right-left)>(rightSure-leftSure)){ //求最大值 rightSure = right; leftSure = left; } } } return s.substr(leftSure,rightSure-leftSure+1); //用了substr方法，进行截取字符串，其中第一个参数为截取开始的下标，第二个参数为截取的长度 } }; |
2. 暴力法
选出所有子字符串可能的开始和结束位置，并检验它是不是回文。
3. 动态规划
动态规划的算法核心思想是把多阶段问题转换为单阶段问题
在本题中，可以将字符串回文部分的搜索视为从小到大的过程，即状态方程P(i , j) = ( P(i+1,j-1) && S[i]==S[j] )
这儿需要注意的是，我们采用从小到大的思路去解决问题。因此这儿逐渐要从最小的量到最大的量，因此我们可以从串的长度入手，从小到大。而动态扫描的指标是数组的下标。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { public: string longestPalindrome(string s) { //动态规划解法 int len = s.length(); int max = 1; int start = 0; vector<vector<int>> dp(len,vector<int>(len)); if(len<2){ return s; } //赋初值 for(int i=0;i<len-1;i++){ dp[i][i] = 1; if(s[i]==s[i+1]){ dp[i][i+1] = 1; max = 2; start = i; } } //动态规划 for(int i=3;i<=len;i++){ for(int j=0;j<len-i+1;j++){ if(s[j]==s[j+i-1]&&dp[j+1][j+i-2]==1){ dp[j][j+i-1]=1; max = i; start = j; } } } return s.substr(start,max); } }; |
4. 马拉车算法
等待更新（https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/）
