Leetcode-214-Shortest Palindrome

在给定字符串前面添加若干字符使得字符串变成回文字符串，问回文字符串中最短的字符串是什么。

这题的思路很简单，就是找原字符串中以第一个字符开头的最长回文字符串，然后将剩余部分reverse一下加在字符串开头即可。直接写了一个DP，结果1有一个数据点爆栈了……时间换空间的写法又TLE……最终卡在了唯一一个数据点上……

在Discuss区看到一种十分直接的写法如下：

class Solution {
public:
    string shortestPalindrome(string s) {
        string r = s;
        reverse(r.begin(), r.end());

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

其中c_str()把string 对象转换成c中的字符串样式。 memcmp(s1,s2,n)就是比较s1和s2的前n个字节的ascII码值。这样的写法时间空间效率都还可以，果然即使用C++也不能忘了C当中的一些写法啊……