题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

题解

暴力法

暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。

public class Solution 
{
    public string LongestPalindrome(string s)
    {
        if (s.Length == 0) return "";
        var longest = s.Substring(0, 1);
        for (var i = 0; i < s.Length ; i++)
        {
            var s1 = ExpandAroundCenter(s, i, i);
            if (s1.Length > longest.Length) longest = s1;
            var s2 = ExpandAroundCenter(s, i, i + 1);
            if (s2.Length > longest.Length) longest = s2;
        }
        return longest;
    }
    private string ExpandAroundCenter(string s, int left, int right)
    {
        var l = left;
        var r = right;
        while (l >= 0 && r < s.Length && s[l] == s[r])
        {
            l--;
            r++;
        }
        return s.Substring(l + 1, r - (l + 1));
    }
}

动态规划

参考：Grandyang

我们维护一个二维数组 dp，其中 dp[i,j] 表示字符串区间 [i, j] 是否为回文串。

• 当 i = j 时，只有一个字符，肯定是回文串

• 如果 i = j + 1，说明是相邻字符，此时需要判断 s[i] 是否等于 s[j]

• 如果 i 和 j 不相邻，即i - j >= 2时，除了判断 s[i] 和 s[j] 相等之外，dp[j + 1,i - 1] 若为真，就是回文串

通过以上分析，可以写出递推式如下：
dp[i,j] = true if i == j
= s[i] == s[j] if j = i + 1
= s[i] == s[j] && dp[i+1,j-1] if j > i + 1

public static string LongestPalindrome(string s)
{
    if (string.IsNullOrEmpty(s)) return "";
    // dp[i,j] 表示字符串区间 [i,j] 是否为回文串
    var dp = new bool[s.Length, s.Length];
    int left = 0, right = 0, len = 0;
    for (var i = 0; i < s.Length; i++)
    {
        for (var j = 0; j < i; ++j)
        {
            dp[j, i] = s[i] == s[j] && (i - j < 2 || dp[j + 1, i - 1]);
            if (dp[j, i] && len < i - j + 1)
            {
                len = i - j + 1;
                left = j;
                right = i;
            }
        }
        dp[i, i] = 1!=0;
    }
    return s.Substring(left, right - left + 1);
}