leetcode 151 - Longest Palindromic Substring

Longest Palindromic Substring

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.

先解釋什麼叫 palindromic，中文翻譯大概是迴文
也就是說左邊讀過去跟右邊讀回來是一樣對稱的
各國都有這樣的惡搞文化


這種文字遊戲博大精深的中文最能讓人有感覺

上海自來水來自海上
西湖垂柳絲柳垂湖西
山西會仙橋仙會西山
花蓮浣紗女紗浣蓮花
洛河飄香茶香飄河洛
狂風暴雨夜雨暴風狂
中山停雲堂雲停山中
馬下花香聞香花下馬
西湖靈隱寺隱靈湖西
天上龍捲風捲龍上天

英文的則為單字或是句子
單字比較有fu，例如 civic, bed 但是頗無聊

用字母的句子比較沒fu，畢竟英文有斷句，左右拼起來的單字要重組
A Toyota! Race fast, safe car! A Toyota!
Madam, I'm Adam.
Sex at noon taxes.
A man,a plan,a canal - Panama! 

日文也可以很有fu
達人の人達
初音島的DC動畫，朝倉音夢就有個惡搞是 "音夢の胸" 念 ねむのむね
(不知道為什麼記到現在)

離題了...

這次的題目有難到
不管怎麼寫都會卡在 TLE (Time Limit Exceeded)
class Solution {
public:
    string longestPalindrome(string s) {
        int i, j, k, length = 0;
        string target;
        vector<string> svector(0);
     
        for (i=s.size(); i>=1; i--)
        {
            for (j=0; j<s.size(); j++)
            {
                if (i+j <= s.size())
                {
                    target = s.substr(j, i);

                    int same_count = 0;
                    for (k=0; k<target.size(); k++)
                    {
                        int left = k, right = target.size()-1-k;

                        if (left <= right)
                        {
                            if (target[left] == target[right])
                                same_count++;
                        }
                    }
                    if (same_count == (target.size()+1)/2)
                    {
                        i=0;
                        j=s.size();
                    }
                }
            }
        }
       
        return target;
    }
};
bool palindromic(string s)
{
    int right, left;
    int k, same_count = 0;

    for (k=0; k<s.size(); k++)
    {
        left = k;
        right = s.size()-1-k;

        if (left <= right)
        {
            if (s[left] == s[right])
                same_count++;
            else
                break;
        }
    }
    if (same_count == (s.size()+1)/2)
        return true;
    else
        return false;
}

class Solution {
public:
    string longestPalindrome(string s) {
        int start_pos = 0, length = 0;
        int right, left;
        int i, j;
        string target, res;
        bool found;

        for (i=0; i<s.size(); i++)
        {
            found = false;
            right = i;
            left = s.size()-1;
            if (left-i > length)
            {
                while (right <= left && !found)
                {
                    if (s[right] == s[left])
                    {
                        target = s.substr(right, left-right+1);
                        found = palindromic(target);
                    }
                    left--;
                }
                if (found)
                {
                    if (target.size() > length)
                    {
                        length = target.size();
                        res = target;
                    }
                }
                if (length >= s.size()/2)
                    break;
            }
        }
       
        return res;
    }
};
寫了兩種都時間效率太差
腦袋很差真的想不出來了
去找網路資料才知道，這題目竟然有O(N^2)，甚至O(N)的演算法 ...
太扯了，重點是看了還看不懂何況要想到這種演算法才解的了這題 ...
直接參考網路的 code 來寫 ... (偷懶)
O(N^2)的演算法是 DP, dynamic programming
O(N)的演算法是 Manacher's algorithm
以下為 O(N) 的方法
int match(string s, int N, int a, int b)
{
    int i = 0;
    while (a-i>=0 && b+i<N && s[a-i] == s[b+i]) i++;
    return i;
}

class Solution {
public:
    string longestPalindrome(string s) {
        string s2, res;
        int Z[10001 * 2], L, R;

        int N = s.size();

        s2.assign(N*2+1, '.');
        for (int i=0; i<N; i++)
            s2[i*2+1] = s[i];
        N = N*2+1;

        Z[0] = 1;
        L = R = 0;
        for (int i=1; i<N; ++i)
        {
            int ii = L - (i - L);
            int n = R + 1 - i;

            if (i > R)
            {
                Z[i] = match(s2, N, i, i);
                L = i;
                R = i + Z[i] - 1;
            }
            else if (Z[ii] == n)
            {
                Z[i] = n + match(s2, N, i-n, i+n);
                L = i;
                R = i + Z[i] - 1;
            }
            else
            {
                Z[i] = min(Z[ii], n);
            }
        }

        int n = 0, p = 0;
        for (int i=0; i<N; ++i)
            if (Z[i] > n)
                n = Z[p = i];

        for (int i=p-Z[p]+1; i<=p+Z[p]-1; ++i)
            if (i & 1)
                res.push_back(s2[i]);

        return res;
    }
};