问题
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
思路
验证回文串的方法就是两个两个的对称验证是否相等。查找回文字串的方法，就要以每一个字符为中心，像两边扩散来寻找回文串，这个算法的时间复杂度是O(n*n)，由于回文串的长度可奇可偶，需要注意下奇偶情况，比如”bob”是奇数形式的回文，”noon”就是偶数形式的回文。
class Solution {
public:
void findPalindrome(string s, int left, int right, int &startIndex, int &maxLen){
int step = 1;
while((left - step) >= 0 && (right + step) <= s.length())
{
if(s[left - step] != s[right + step])
{
break;
}
++step;
}
int wide = right - left + 2 * step - 1; //step初始化为1，包含中心点，减去1
if(maxLen < wide) //当前长度大于之前的len，即更新
{
maxLen = wide;
startIndex = left - step + 1; //left包含在step中，加1
}
}
string longestPalindrome(string s) {
int len = s.length();
int left = 0;
int right = 0;
int startIndex = 0;
int maxLen = 0;
for(int i = 0; i < len; ++i)
{
if(s[i] == s[i + 1])
{
left = i;
right = i + 1;
findPalindrome(s, left, right, startIndex, maxLen);
}
left = i;
right = i; //出现相同字符的情况，需要再判断奇回文的情况，例如ccc
findPalindrome(s, left, right, startIndex, maxLen);
}
return s.substr(startIndex, maxLen);
}
};
动态规划的解法，维护一个dp[i][j]的二维数组，其元素值表示的是从i到j，是否为回文串。值得注意的地方是：当i，j不相邻的情况，需另外确认dp[i+1][j-1]是否为回文串。
下面是一开始写的代码。没有考虑清楚i,j的遍历范围。动态数组的值，必须是根据前面已知值，推后续值。条件分类也可以再简化。
class Solution {
public:
string longestPalindrome(string s) {
int len = s.length();
int left = 0;
int right = 0;
int maxLen = 0;
int dp[len][len] = {0};
for(int i = 0; i < len; ++i)
{
for(int j = 0; j < len; ++j)
{
if(j == i)
{
dp[i][j] = 1;
}
else if(j == i + 1)
{
if(s[i] == s[j])
{
dp[i][j] = 1;
}
}
else if(j > i + 1) //dp[i + 1][j - 1]还未计算
{
if(s[i] == s[j] && dp[i + 1][j - 1] == 1)
{
dp[i][j] = 1;
}
}
}
}
return s.substr(startIndex, maxLen);
}
};
特殊之处在于，一维在j，二维在i。这样保证了计算当前dp值时，前面值都已计算。
class Solution {
public:
string longestPalindrome(string s) {
int len = s.length();
int left = 0;
int right = 0;
int maxLen = 0;
int dp[len][len] = {0};
for(int i = 0; i < len; ++i)
{
for(int j = 0; j < i; ++j)
{
if((s[j] == s[i]) && (i - j < 2 || dp[j + 1][i - 1] == 1))
{
dp[j][i] = 1;
}
else
{
dp[j][i] = 0;
}
if(dp[j][i] == 1 && maxLen < i - j + 1)
{
maxLen = i - j + 1;
left = j;
right = i;
}
}
dp[i][i] = 1;
}
return s.substr(left, right - left + 1); //substr的第二个参数，不能直接使用maxLen，因为单个元素的字符串会返回为空
}
};
马拉车算法，可达到O(n)的时间复杂度。目前在刷动态规划，优化什么的，之后再说吧。
C++小知识
||只要满足第一个条件，后面的条件就不再判断
通过传引用的方式改变局部变量，代替全局变量的使用。
二维数组和二维向量的创建与初始化：int dp[s.size()][s.size()] = {0}
一维数组的动态分配，初始化和撤销：
动态分配： int *array=new int [n]；
初始化： memset(array,0,n*sizeof(array));
撤销： delete [] array;
二维数组的动态分配，先动态分配了一个10单元的数组的指针的指针的首地址给*array，然后再对其每个首地址进行遍历，完成一个5单元的数组的动态分分配，并把首地址给array[i]
int **array;
array=new int *[10];
for(int i=0;i<10;i++)
array[i]=new int [5];
二维数组的动态初始化，memset只作用于一块连续的内存空间
int **array;
array=new int *[10];
for(int i=0;i<10;i++)
{
array[i]=new int [5];
memset(array[i],0,5*sizeof(int)); //注意这里是array[i]
}
二维数组的撤销，先里层再外层
for (int i = 0; i < 10; i ++)
{
delete[] array[i];
}
delete [] array；