LeetCode题集-5 - 最长回文子串（一）
标题：给你一个字符串 s，找到 s 中最长的回文子串。
这一题作为中等难度，惯例解法关于大多数人应该都没有难度。可是其间也有超难的解决办法，下面咱们就一同由易到难，按部就班地来解这道题。
01、暴力破解法
关于大多数标题来说，在不考虑功能的状况下，暴力破解法常常是最契合人的思维习惯的。
比方这道题，求一个字符串中最长的回文子串，那么咱们只需求把字符串中一切或许的子字符串都判别一下是不是回文串，并找出长度最长的不就行了嘛。
这儿需求三层循环，榜首层和第二层循环组织出一切或许的子字符串，第三层循环判别是否为回文串。
而判别一个字符串是否为回文串，也很简单，只需求从字符串两头开端判别首尾字符是否持平，假如持平持续向字符串中心方向行进持续比较下一个首尾字符是否持平，直到比较完一切字符，假如都持平则为回文串。其间心思维是由外向内，逐个比较。
具体代码如下：
//暴力破解法
public static string BruteForce(string s)
{
var result = string.Empty;
var max = 0;
var len = s.Length;
//从榜首个字符开端遍历，作为开端字符
for (var i = 0; i < len; i++)
{
//从第二个字符来开端遍历，作为完毕字符
for (var j = i + 1; j <= len; j++)
{
//取出[i,j)字符串,即包括i，欠好含j，为暂时字符串
var temp = s[i..j];
//假如暂时字符串是回文字符串，且暂时字符串长度大于方针字符串长度
if (IsPalindromic(temp) && temp.Length > result.Length)
{
//则更新方针字符串为当时暂时字符串
result = temp;
max = Math.Max(max, j - i - 1);
}
}
}
return result;
}
//判别字符串是否为回文串
public static bool IsPalindromic(string s)
{
var len = s.Length;
//遍历字符串的一半长度
for (var i = 0; i < len / 2; i++)
{
//假如对称方位不同，则不为回文串
if (s[i] != s[len - i - 1])
{
return false;
}
}
return true;
}
时刻杂乱度：两层for循环O(n^2），for 循环里面判别是否为回文串O(n），所以时刻杂乱度为O(n^3）。
空间杂乱度：O(1），常数个变量。
02、暴力破解法优化（动态规划法）
要想优化暴力破解法，咱们要先找到它到底有什么问题。它的时刻杂乱度之所以这么高，是因为有很多的重复核算，或许文字描述不行直观，下面咱们先用二维表展示一个字符串的一切子字符串的组合状况，然后再在这个表中看判别是否为回文串时哪些子字符串被重复判别。
如上图在字符串abcde中，在判别其子字符串bcd是否是回文串时，作为字符串bcd现已核算过了，相同的其子字符串c，作为字符串也现已核算过了，其他的沿着箭头方向都是表明存在重复核算的当地。
到这儿咱们的优化计划就有了，咱们能够把现已核算过的存下来，这样下次用到的时分直接拿过来用而不必再核算了。
已然咱们经过图就发现了一些规则，咱们无妨再深化考虑一下，为什么会这样？
假如咱们根据暴力破解法中判别是否为回文串的算法界说回文串，那么可得：
P(i,j)=P(i+1,j-1)&&S[i]==S[j]
能够理解为假如一个字符串是回文串，那么去掉首尾字符后子字符串依然是回文串。反过来假如子字符串是回文串而且其首尾一个字符持平，那么这个字符串全体也是回文串。
咱们再对上图斜对角上加些辅助线，假如咱们按一切子字符串的长度分类，则会发现长度为3的依靠长度为1的，长度为5的依靠长度为3的，长度为4的依靠长度为2的。如下图：
长度为1本身便是回文串，长度为2的假如两个字符持平则为回文串，那么一切长度大于等于3的都能够经过长度为1和2的核算出来。
到这儿整个算法思路就出来了：先核算长度为1和2的子字符串并存入二维数组，然后根据此二维数组持续核算长度为3、4、5……。
具体代码如下：
//动态规划
public static string DynamicProgramming(string s)
{
var length = s.Length;
//判别该组合是否是回文字符串，行为开端点，列为完毕点
var dp = new bool[length, length];
//最长回文字符串，初始为0
var result = string.Empty;
//从回文长度为1开端判别，到字符长度n停止
for (var len = 1; len <= length; len++)
{
for (var startIndex = 0; startIndex < length; startIndex++)
{
//完毕索引 = 开端索引 + 距离（len - 1）
var endIndex = startIndex + len - 1;
//完毕索引超出字符串长度，完毕本次循环
if (endIndex >= length)
{
break;
}
//回文字符串的公式便是子字符串也是回文，而且当时开端字符和完毕字符持平，
//所以得出公式 dp[startIndex+1,endIndex-1] && s[startIndex] == s[endIndex]
//其间回文长度为1和2两种特殊状况需求独自处理，其特殊性在于他们不存在子字符串
//回文长度为1时，本身当然等于本身
//回文长度为2时，开端字符和完毕字符是相邻的，只需相邻的字符持平就能够
dp[startIndex, endIndex] = (len == 1 || len == 2 || dp[startIndex + 1, endIndex - 1]) && s[startIndex] == s[endIndex];
//当时字符串是回文，而且当时回文长度大于最长回文长度时，修正result
if (dp[startIndex, endIndex] && len > result.Length)
{
result = s.Substring(startIndex, len);
}
}
}
return result;
}
时刻杂乱度：O(n^2），即为两层for循环组成的一切子字符串状况。
空间杂乱度：O(n^2)，即存储已核算子字符串成果需求的空间。
这个算法还有一个专有称号：动态规划，咱们这儿之所以没有突出去讲，是想把整个解题思路展示出来，把握好了根底解题才能，咱们才能做总结，而这个解法的总结就能够归纳为动态规划，这是一种通用的思维，后边会经常用到。
03、中心扩展法
上面的优化尽管时刻杂乱度降下来了，可是空间杂乱度上升了，咱们持续想想有什么其他办法呢？
上面的办法判别是否为回文串的中心思维是由外向内，那咱们是否能够换个思路——从内向外呢？这便是中心扩展法的中心思维。
在暴力破解法中，咱们需求两层循环表明任何一种子字符串摆放，而且中心扩展法中心思维是经过一个中心点向两头扩展也就天然只需求一层循环即可表明勘探一切字符的状况。
由中心往两头扩展是对称的，而回文串长度能够是奇数也能够是偶数，因而咱们在中心扩展时就需求分奇偶两种状况来处理。
到这儿咱们能够大致整理一下全体逻辑了：
（1）顺次循环处理字符串的每个字符，向两头扩展；
（2）每次扩展分奇偶两种状况处理；
（3）核算出最大长度并保存；
（4）重复（2）、（3）直至一切字符处理完结；
具体完成代码如下：
//中心分散法
public static string CenterExpand(string s)
{
//假如字符串为空或只要一个字符，直接回来该字符串
if (s == null || s.Length < 1)
{
return "";
}
//记载最长回文子串的开端方位和完毕方位
var startIndex = 0;
var endIndex = 0;
//遍历每个字符，一起处理回文字串长度为奇偶的状况，
//即以该字符或该字符与其下一个字符之间为中心的回文
for (var i = 0; i < s.Length; i++)
{
//获取回文字串长度为奇数的状况，
//即以当时字符为中心的回文长度
var oddLength = PalindromicLength(s, i, i);
//获取回文字串长度为偶数的状况，
//即以当时字符和下一个字符之间的空地为中心的回文长度
var evenLength = PalindromicLength(s, i, i + 1);
//取两种状况下的最长长度
var maxLength = Math.Max(oddLength, evenLength);
//假如找到更长的回文子串，更新开端方位和长度
if (maxLength > endIndex - startIndex)
{
//从头核算开端方位
startIndex = i - (maxLength - 1) / 2;
//从头核算完毕方位
endIndex = i + maxLength / 2;
}
}
//回来最长回文子串
return s[startIndex..(endIndex + 1)];
}
//从中心向外扩展，查看并回来回文串的长度
public static int PalindromicLength(string s, int leftIndex, int rightIndex)
{
//左鸿沟大于等于首字符，右鸿沟小于等于尾字符，而且左右字符持平
while (leftIndex >= 0 && rightIndex < s.Length && s[leftIndex] == s[rightIndex])
{
//从中心往两头扩展一位
//向左扩展
--leftIndex;
//向右扩展
++rightIndex;
}
//回来回文串的长度（留意原本应该是rightIndex - leftIndex + 1，
//可是满意条件后leftIndex、rightIndex又分别向左和右又各扩展了一位，
//因而需求把这两位减掉，所以最终公式为rightIndex - leftIndex - 1）
return rightIndex - leftIndex - 1;
}
时刻杂乱度：O(n^2)。
空间杂乱度：O(1)。
此办法尽管时刻杂乱度没变，可是空间杂乱度大大下降。这也给了咱们持续优化的动力。
下一章节咱们将具体解说次题的马拉车解法。
注：测验办法代码以及示例源码都现已上传至代码库，有爱好的能够看看。https://gitee.com/hugogoos/Planner
