LeetCode 5 Longest Palindromic Substring（最大回文子字符串）

LeetCode 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);
    }
}

然而，繼續悲劇……

Submission Result: Memory Limit Exceeded

public class Solution
{
    public string LongestPalindrome(string s)
    {
        int nLen = s.Length;
        if (nLen == 0) return ;
        string lonStr = s.Substring(0, 1);
        for (int i = 0; i < nLen - 1; i++)
        {
            string p1 = ExpandAroundCenter(s, i, i);
            if (p1.Length > lonStr.Length)
                lonStr = p1;
            string p2 = ExpandAroundCenter(s, i, i + 1);
            if (p2.Length > lonStr.Length)
                lonStr = p2;
        }
        return lonStr;
    }
    public static string ExpandAroundCenter(string s, int n, int m)
    {
        int l = n, r = m;
        int nLen = s.Length;
        while (l >= 0 && r <= nLen - 1 && s[l] == s[r])
        {
            l--;
            r++;
        }
        return s.Substring(l + 1, r - l - 1);
    }
}

好吧，這種方法來源於網絡……據說要O(n2)的時間，但僅要O(1)的空間！