谷歌电面2

电面2
第一题isPalindrome
第二题给一个字符 返回最小的切割次数，使得每个子串都是回文字符
第二题用的dfs+memoization search，花了大概不到10分钟写完了

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

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

trong>
大米给给Thanks♪(･ω･)ﾉ

zorrowei 发表于 2019-3-2 07:18
第二题贴个加密钥匙的代码给我们观摩、膜拜一下吧！谢谢！

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

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

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

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

congrats! 樓主太強

感谢分享，LZ第二题是怎么做的呢

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

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

你第二题是怎么做的？动规二次方的时间复杂度的解法?

第二题贴个加密钥匙的代码给我们观摩、膜拜一下吧！谢谢！

动态规划是O(n^2)的，dfs+memorization的话，也能做到O(n^2)，但是不只需要对dfs的结果进行记忆化，还需要对一个子串是否是回文字符串进行记忆化
否则的话，单纯是dfs中判断当前子串是不是回文串，总时间复杂度也到O(n^3)了

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

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

说的太专业了，刺激我继续刷题