最长回文子串

题目

给你一个字符串s，找到s中最长的回文子串。
** 回文子串指 abcba 等对称结构的字符串。

题解1：动态规划（Dynamic Programming)

思路源自程序员Carl，他在Github上创建了名为力扣刷题攻略的项目，链接贴在文末。

Carl在题解中提及了动规五部曲：

确定dp数组以及下标的含义。
确定递推公式。
dp数组如何初始化。
确定遍历顺序。
举例推导dp数组。

在实际解决动规问题时，可以通过上述步骤为自己提供一个比较清晰的思路，接下来将详细阐述本题中每个步骤需要考虑的内容。

1.确定dp数组以及下标的含义

本题中将动规数组声明为布尔类型的二维数组，其中下标为 i、j 的元素表示字符串 s 从下标 i 至下标 j 之间的子串是否为回文子串。

2.确定递推公式

寻找当前元素与值已知的元素之间的联系，是推导递推公式的关键。
假定 i、j 为子串的头元素与尾元素的下标，探究该子串是否为回文串，实际可能的情况有以下几种：

s[i] ≠ s[j]：毋庸置疑该子串不是回文串；
s[i] == s[j]：这种情况要分点讨论：
①若 i == j，则s[i]与s[j]为同一元素，必然为回文串；
②若 i == j - 1，必然为回文串；
③若 j - i > 1，则【i，j】区间的子串是否为回文串需要看【i + 1，j - 1】区间的子串是否为回文串。

这部分判断逻辑的代码实现如下：

if(s[i] == s[j] && (j - i <= 1 || dp[i + 1, j - 1] == 1))
{
	dp[i, j] = 1;
    if(j - i + 1 > maxLength)
	{
		maxLength = j - i + 1;
		left = i;
	}
}

3.dp数组如何初始化

因为 dp【i，j】代表了区间【i，j】之间的子串是否为回文串，所以初始化值为0，代表着false；在验证了子串为回文串才重新赋值为1，代表true。

4.确定遍历顺序

dp【i，j】的值由dp【i + 1，j - 1】推导，后者位于前者的左下方位置，所以遍历顺序有以下两种：①以行为主，行从大往小遍历，列从左往右遍历；②以列为主，列从左往右遍历，行从上往下遍历。

5.举例推导dp数组

实际问题中多举例验证即可。

代码部分

时间复杂度O（n²），空间复杂度O（n²）

public class Solution {   
    public string LongestPalindrome(string s) {
        int left = 0;
        int maxLength = 0;
        int[,] dp = new int[s.Length, s.Length];

        for(int j = 0; j < s.Length; j++)
            for(int i = 0; i <= j; i++)
            {
                if(s[i] == s[j] && (j - i <= 1 || dp[i + 1, j - 1] == 1))
                {
                    dp[i, j] = 1;
                    if(j - i + 1 > maxLength)
                    {
                        maxLength = j - i + 1;
                        left = i;
                    }
                } 
            }
        
        return s.Substring(left, maxLength);
    }
}

题解2：双指针

首先要考虑两件事：①枚举所有可能的子串；②判断子串是否为回文串。
如何判断子串是否为回文串？回文串的特点是关于中心呈两端对称，中心可以是长度为一或长度为二的回文串，单个字符毋庸置疑是回文串，长度为二的情况下需要两个字符相等的字符串才符合条件。对字符串s中的每一个字符进行遍历，单次操作考虑以上两种情况，从选定的中心点每次往两边扩展一个单位的字符，根据比对结果决定是否继续扩展，即可将所有可能的子串都纳入考虑范围。以下是双指针思路下的C#解题代码：
时间复杂度：O（n²），空间复杂度：O（1）；

public class Solution {   
    int left = 0;
    int maxLength = 1;
    
    public string LongestPalindrome(string s) {
        for(int i = 0; i < s.Length - 1; i++)
        {
            FindPalindrome(s, i, i);
            FindPalindrome(s, i, i + 1);
        }
        
        return s.Substring(left, maxLength);
    }

    public void FindPalindrome(string s, int l, int r)
    {
        while(l >= 0 && r < s.Length && s[l] == s[r])
        {
            if(maxLength < r - l + 1)
            {
                maxLength = r - l + 1;
                left = l;
            }
            l--;    r++;
        }
    }
}