10钟前google电面

写lz分享，题目不错，从naive-时间优化-dp-空间优化，各种follow up，很好的一题

string题，第一问和leetcode上的shortest palindrome 基本一样，换成了插在结尾，问题不大，讨论了下时间复杂度。
follow up问如果插字符在任何地方，看到过dp解法，但是想不起来也没推出来。搜了一下，类似 pku1159，
follow-up写了一下，大家看一下是否对了呢？
题意就是 求一个字符串最少用多少个字符使得整个字符串成为回文串。
Ab3bd,返回2

class Solution
{
public:
        int addChar(string str)
        {
                if(str.size() < 2)
                        return 0;

                string revStr(str.rbegin(), str.rend());

                return str.size() - LCS(str, revStr);
        }

        int LCS(string a, string b)
        {
                if(a.size() < 1 || b.size() < 1)
                        return 0;
                vector<int> pre(b.size()+1);

                for(int i = 1; i <= a.size(); i++)
                {
                        vector<int> cur(b.size()+1);
                        for(int j = 1; j <= b.size(); j++)
                        {
                                if(a[i-1] == b[j-1])
                                        cur[j] = pre[j-1] + 1;
                                else
                                        cur[j] = max(cur[j-1], pre[j]);
                        }
                        pre = cur;
                }
                return pre[b.size()];
        }
};


//int main()
//{
//        string str("AC");
//        Solution ss;
//        cout<<ss.addChar(str);
//        int i = 0;
//}

感觉是不是可以反转字符串然后用longest common subsequence做？

laurie洁 发表于 2015-8-29 03:28
尝试了一下dp解法：dp[j]存从s到s[j]的substring能够组成的最短palindrome

非常赞的思路！启发很大！

这还不叫黑。。。。。。。

什么叫shortest palindrome呀，只知道longest palindrome.

感谢分享，楼主有拿onsite吗？