狗家店面面筋

今天早上刚面的，利口 三酒撕，中等题， 其实比利口简单一些，因为数字只要求在1-9之间。我是用递归的方法，一个counter算括号位置。
复杂度我分析是平均O(nlogn)最坏O(n^2) 不知道对不对，希望大家指教一下这

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

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

长度的函数会在一个子串上重复调用，也许可以用记忆化搜索吧。复杂度O(nlogn)。 不知道有没有更好的方法呢？

楼主，第二题能详细说说嘛

hzyfree 发表于 2017-10-6 15:00
楼主，第二题能详细说说嘛

比如ab3[2[ef]cd]展开后是abefefcdefefcdefefcd 如果给你下标5你要返回f

baudelaire 发表于 2017-10-6 20:03
比如ab3[2[ef]cd]展开后是abefefcdefefcdefefcd 如果给你下标5你要返回f

噢噢我没看到这是follow up， 还以为是单独的一道题。。。

楼主能分享一下，space complexity是怎么想的嘛

renhh 发表于 2017-10-8 00:13
楼主能分享一下，space complexity是怎么想的嘛

面试官没让分析这个 不过我觉得应该是展开后的字符串的长度

baudelaire 发表于 2017-10-8 04:57
面试官没让分析这个 不过我觉得应该是展开后的字符串的长度

我也觉得space complexity 是展开后的长度
那个O(nlogn)是指什么 runtime么？
这个runtime到底应该是什么呀
谢谢

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

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

感谢分享！ 楼主有结果了吗？ 祝好运！

我觉得用一个stk保存数字，一个 cnt 记录当前已经访问到的char，当碰到], stkPop() * size_parenthesized.
复杂度好像是O（n），space O（n/2） at most