最长回文子串

题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例
（1）输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
（2）输入: “cbbd”
输出: “bb”

解题思路
分析：要判断一个字符串是否是回文串，需要以下两步才能判断其是否为回文串：（1）其子串为回文串（2）在子串的基础上左右分别加一个相等的字符；

dp[left, right] = (s[left] == s[right] && (right - left < 2 || dp[left + 1, right - 1]));

那么在这个过程中，就必须记录其子串是否为回文串，所以，实现的代码中给出了一个bool类型的二维数组，用来保存其子串是否为回文的判定结果。

bool[,] dp =new bool[s.Length, s.Length];

另外，在此过程中要实时更新最长的回文串，只有当目前的回文串的长度比保存的最长的回文串长时才需要将其更新。

result = dp[left, right] && result.Length < s.Substring(left, right - left + 1).Length ? s.Substring(left, right - left + 1) : result;

代码（C#实现）

public static string LongestPalindrome(string s)
        {
            string result = "";
            bool[,] dp =new bool[s.Length, s.Length];
            for (int right = 0; right < s.Length; right++)
            {
                for (int left = 0; left <= right; left++)
                { 
                    dp[left, right] = (s[left] == s[right] && (right - left < 2 || dp[left + 1, right - 1]));
                    result = dp[left, right] && result.Length < s.Substring(left, right - left + 1).Length ? s.Substring(left, right - left + 1) : result;
                }
            }
            return result;
        }

运行结果
输入：“babad”