題目

214. Shortest Palindrome
難度: 難!

題意

給定一字串s，在s前加入字元使s成為回文。
範例1
Input: s = "aacecaaa"
Output: "aaacecaaa"

範例2
Input: s = "abcd"
Output: "dcbabcd"

思路

檢查從頭開始最長的回文，剩下不是回文的部分，反轉再接回去原字串的前方。

範例1
Input: s = "aacecaaa"
檢查到最長回文"aacecaa"，剩餘字串"a"反轉接回去原字串前方，變成"aaacecaaa"
範例2
Input: s = "abcd"
檢查到最長回文"a"，剩餘字串"bcd"反轉接回去原字串前方，變成"dcbabcd"

實作1

brute force法

class Solution {
private:
    bool is_palindrome(const string& s, const int len)
    {
        for(int i = 0; i < len / 2; i++)
            if(s[i] != s[len -1 - i])
                return false;
        return true;
    }
public:
    string shortestPalindrome(string s) {
        int n = (int)s.length();
        // Length of already palindrome
        int max_len = 0;
        for(int len = 0; len < n; len++)
        {
            if(is_palindrome(s, len))
                max_len = len;
        }

        string front;
        for(int i = max_len; i < n; i++)
            front.push_back(s[i]);
        reverse(front.begin(), front.end());
        return front + s;
    }
};

結果1

Wrong Answer 118 / 123 test cases passed.
Input:
"a"
Output:
"aa"
Expected:
"a"

粗心，len應該檢查到與s等長

實作2

修正了檢查回文的總長度到與s等長

class Solution {
private:
    bool is_palindrome(const string& s, const int len)
    {
        for(int i = 0; i < len / 2; i++)
            if(s[i] != s[len -1 - i])
                return false;
        return true;
    }
public:
    string shortestPalindrome(string s) {
        int n = (int)s.length();
        // Length of already palindrome
        int max_len = 0;
        for(int len = 0; len <= n; len++)
        {
            if(is_palindrome(s, len))
                max_len = len;
        }

        string front;
        for(int i = max_len; i < n; i++)
            front.push_back(s[i]);
        reverse(front.begin(), front.end());
        return front + s;
    }
};

結果2

Time Limit Exceeded 121 / 123 test cases passed.
錯誤測資為長度5 * 10^4的'b'
不出所料TLE
暴力法O(N^2)，在10^4大小不太可能AC

實作3

投機取巧，預先判斷整個字串是否皆為同一字元，如果是的話，就不進行檢查回文以節省時間。

        // String has same char in the current length
        bool single = true;
        for (int len = 1; len <= n; len++)
        {
            if (s[len - 1] != s[0])
                single = false;
            if (single || is_palindrome(s, len))
                max_len = len;
        }

結果3

Time Limit Exceeded 122 / 123 test cases passed.
錯誤測資為超長的"ababa....ab"

實作4

突然想到，既然要檢查最長的已存在回文，那從長的那端開始檢查不就行了?
修改為如下，同時把投機取巧移除:

    string shortestPalindrome(string s)
    {
        int n = (int) s.length();
        // Length of already palindrome
        int max_len = 0;
        for (int len = n; len >= 1; len--)
        {
            if (is_palindrome(s, len))
            {
                max_len = len;
                break;
            }
        }

        string front;
        for (int i = max_len; i < n; i++)
            front.push_back(s[i]);
        reverse(front.begin(), front.end());
        return front + s;
    }

結果4

Time Limit Exceeded 122 / 123 test cases passed.
仍然卡在最後一筆測資

實作5

預先翻轉字串s，交給memcmp來比較，移除自己刻的檢查回文函式:

class Solution
{
public:
    string shortestPalindrome(string s)
    {
        const int n = (int)s.length();
        // A reverse of s
        string r = s;
	    reverse(r.begin(), r.end());

	    for (int i = 0; i < n; ++i) {
            if (!memcmp(s, r + i, (r.size() - i) / 2)) {
               return r.substr(0, i) + s;
            }
        }
        return r + s;
    }
};

結果5

Compile Error
原來memcmp不能填r + i嗎XD

實作6 7

修改memcmp的呼叫方式

class Solution
{
public:
    string shortestPalindrome(string s)
    {
        const int n = (int)s.length();
        // A reverse of s
        string r = s;
	    reverse(r.begin(), r.end());

	    for (int i = 0; i < n; ++i) {
            if (!memcmp(s.c_str(), r.c_str() + i, (r.size() - i) / 2)) {
               return r.substr(0, i) + s;
            }
        }
        return r + s;
    }
};

結果6 7

Accepted
123/123 cases passed (14 ms)
Your runtime beats 12.38 % of cpp submissions
Your memory usage beats 90.93 % of cpp submissions (9.6 MB)
竟然能過XDD

分析

若字串長度N
時間複雜度: O(N^2)，最差就是全部長度都測是否回文
空間複雜度: O(N)，預存反轉字串
但這題因為能做early return，不一定會查完所有的長度，所以能AC算是僥倖
這題要考的應該是Rolling Hash的技巧，對於在字串中尋找某字串，或是統計某字串的出現字數很有用。
但目前還不是很熟練。

總結