5.Longest Palindromic Substring

翻译

给定一个字符串 S，找出它的最大回文子字符串。
你可以假定 S 的最大长度为 1000，
并且这里存在唯一一个最大回文子字符串。

原文

Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000,
and there exists one unique longest palindromic substring.

暴力搜索，O(n3)

public static string LongestPalindrome(string s)
{
    int len = s.Length;
    for (int i = len; i > 0; i--)
        for (int j = 1; j <= len + 1 - i; j++)
            if (isPalindrome(s.Substring(j - 1, i)))
                return s.Substring(j - 1, i);
    return null;
}

public static bool isPalindrome(string s)
{
    for (int i = 0; i < s.Length / 2; i++)
        if (s.Substring(i, 1) != s.Substring(s.Length - 1 - i, 1))
            return false;

    return true;
}

动态规划，时间：O(n2)，空间：O(n2)

public class Solution
{
    public string LongestPalindrome(string s)
    {
        int sLen = s.Length;
        int lonBeg = 0; int maxLen = 1;
        bool[,] DP = new bool[1000, 1000];
        for (int i = 0; i < sLen; i++)
        {
            DP[i, i] = true;
        }
        for (int i = 0; i < sLen - 1; i++)
        {
            if (s[i] == s[i + 1])
            {
                DP[i, i + 1] = true;
                lonBeg = i;
                maxLen = 2;
            }
        }
        for (int len = 3; len <= sLen; len++)      // 字符串长度从3开始的所有子字符串
        {
            for (int i = 0; i < sLen + 1 - len; i++)
            {
                int j = len - 1 + i;       // j为数组尾部的索引
                if (s[i] == s[j] && DP[i + 1, j - 1])
                {
                    DP[i, j] = true;      // i到j为回文
                    lonBeg = i;           // lonBeg为起始索引，等于i
                    maxLen = len;      // maxLen为字符串长度
                }
            }
        }
        return s.Substring(lonBeg, maxLen);
    }
}

然而，继续悲剧……