facebook 电面

直接枚举对称中点O(n)，然后枚举长度O(n)，计数就行，也是O(n^2)的。

最近也有同学被问这题， 要求o(1)空间复杂度

njuprincerain 发表于 2014-11-24 22:48
最近也有同学被问这题， 要求o(1)空间复杂度

O(1)空间就是楼上说的枚举吧？不用DP的那种O(N^2)的算法

是的， 因为用了dp然后悲剧

这道题你用DP还不如不用，使用DP的话是严格O(n^2)的复杂度，而使用枚举的话严格复杂度是O(nk)，其中k是最长回文的回文半径。这样可以达到O(1)空间

为什么aba是4，abba是6？？？？能枚举一下吗

lilihao2014 发表于 2014-11-26 02:36
为什么aba是4，abba是6？？？？能枚举一下吗

aba:
{a, b, a, aba}

abba:
{a, b, b, a, bb, abba}

每一个single character 也是一个 palindrome string

dragonmigo 发表于 2014-11-26 04:23
aba:
{a, b, a, aba}

懂了懂了！O(∩_∩)O谢谢

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies