10钟前google电面

donghao 发表于 2015-8-29 04:26
第二个题目 任何 位置应该可以dp接， geeksforgeeks有原题

dp可以，以前学习过但面试时候没有解出来...

请问只有一道题吗

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

dp[i][i + len - 1] = dp[i + 1][i + len - 1].length() < dp[i][i + len - 2].length() ?
                                s.charAt(i) + dp[i + 1][i + len - 1] + s.charAt(i) : s.charAt(i + len - 1) + dp[i][i + len - 2] + s.charAt(i + len - 1);

这块是不是在字符串前面也插了啊，不是只能在后面插么？

sevenwonder 发表于 2015-8-29 11:26
dp = dp.length() < dp.length() ?
                                s.charAt(i) + dp + s.charAt(i) : ...

这是follow-up的解答

follow up有点难啊

感谢分享~~~

laurie洁 发表于 2015-8-29 12:58
这是follow-up的解答

哦。大牛dp用的很熟练啊，看你很多题dp很快就解出来了膜拜啊！

sevenwonder 发表于 2015-8-29 22:40
哦。大牛dp用的很熟练啊，看你很多题dp很快就解出来了膜拜啊！

绝对不是大牛，小牛都不是~哈哈
参考了网上的解法啦~

follow up怎么这么难。。。。。

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

代码不错，还可以考虑follow up进行空间压缩（滚动数组）